fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. #define fast ios_base::sync_with_stdio(false);
  6.  
  7. int mod=1e9+7;
  8.  
  9. struct obj
  10. {
  11.   int l,r,i,idx;
  12.  
  13. };
  14.  
  15. int a[200001];
  16. obj b[200001];
  17. int freq[200001];
  18. int ans[200001];
  19. unordered_map<int,int>cnt;
  20. bool comp(const obj &x, const obj &y)
  21. {
  22.   if(x.i<y.i)return true;
  23.  
  24.   if(x.i==y.i)return x.r<y.r;
  25.  
  26.   return false;
  27. }
  28. int32_t main()
  29. {
  30.  
  31.   fast;
  32.   cin.tie(NULL);
  33.  
  34. #ifndef ONLINE_JUDGE
  35.   freopen("input.txt", "r", stdin);
  36.   freopen("output.txt", "w", stdout);
  37. #endif 
  38.  
  39.  
  40. int t=1;
  41. // cin>>t;
  42. while(t--)
  43. {
  44.  
  45. int n,q;
  46. cin>>n>>q;
  47.  
  48.  
  49. int curr=1;
  50. for(int i=0;i<n;i++)
  51. {
  52.   cin>>a[i];
  53.  if(cnt.find(a[i])!=cnt.end())
  54.  {
  55.    a[i]=cnt[a[i]];
  56.  
  57.  
  58.  }
  59.  else
  60.  {
  61.    cnt[a[i]]=curr;
  62.   a[i]=curr;
  63.  
  64.   curr++;
  65.  
  66.  
  67.  }
  68.  
  69. }
  70.  
  71. int len=555;
  72. for(int i=0;i<q;i++)
  73. {
  74.   cin>>b[i].l>>b[i].r;
  75.   b[i].l--;
  76.   b[i].r--;
  77.   b[i].i=(b[i].l)/len;
  78.   b[i].idx=i;
  79. }
  80.  
  81.  
  82. sort(b,b+q,comp);
  83.  
  84.  
  85.  
  86. // fill(freq,freq+n+1,0);
  87. int distinct=0;
  88. int L=b[0].l;
  89. int R=b[0].l;
  90. freq[a[L]]++;
  91. distinct++;
  92.  
  93.  
  94. for(int i=0;i<q;i++)
  95. {
  96.  
  97. int l=b[i].l;
  98. int r=b[i].r;
  99. // cout<<l<<" "<<r<<" "<<L<<" "<<R<<endl;
  100. while(r>R)
  101. {
  102.   R++;
  103. if(freq[a[R]]==0) distinct++;
  104. freq[a[R]]++;
  105.  
  106.  
  107. }
  108. while(L>l)
  109. {
  110.     L--;
  111.     if(freq[a[L]]==0) distinct++;
  112.   freq[a[L]]++;
  113.  
  114.  
  115. }
  116. while(l>L)
  117. {
  118.   freq[a[L]]--;
  119.   if(freq[a[L]]==0) distinct--;;
  120.   L++;
  121.  
  122. }
  123. while(R>r)
  124. {
  125.   freq[a[R]]--;
  126.    if(freq[a[R]]==0) distinct--;
  127.  R--;
  128. }
  129.  
  130.  
  131. ans[b[i].idx]=distinct;
  132.  
  133.  
  134. }
  135.  
  136.  
  137. for(int i=0;i<q;i++)
  138. {
  139.   cout<<ans[i]<<'\n';
  140. }
  141.  
  142. }
  143.  
  144.  
  145.  
  146. }
Success #stdin #stdout 0.01s 7564KB
comments (?)
stdin
copy 
5 3
3 2 3 1 2
1 3
2 4
1 5
stdout
copy 
2
3
3
https://ideone.com/STb2hw
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!