fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int const N = 1 << 15;
  6. int const M = 1 << 18;
  7.  
  8. int n, m;
  9. int a[N];
  10.  
  11. pair<int, pair<int, int>> q[M];
  12.  
  13. bool sort_queries(pair<int, pair<int, int>> const& a, pair<int, pair<int, int>> const& b) {
  14.   return a.second.second < b.second.second;
  15. }
  16.  
  17. int bit[N];
  18.  
  19. void update(int idx, int v) {
  20.   while(idx < N)
  21.     bit[idx] += v, idx += (idx&-idx);
  22. }
  23.  
  24. int query(int idx) {
  25.   int sum = 0;
  26.   while(idx > 0)
  27.     sum += bit[idx], idx -= (idx&-idx);
  28.   return sum;
  29. }
  30.  
  31. int ans[M];
  32.  
  33. int main() {
  34.   scanf("%d",&n);
  35.   for(int i = 1; i <= n; ++i)
  36.     scanf("%d",a+i);
  37.  
  38.   scanf("%d",&m);
  39.   for(int i = 0; i < m; ++i)
  40.     scanf("%d%d",&q[i].second.first,&q[i].second.second), q[i].first = i;
  41.  
  42.   sort(q,q+m,sort_queries);
  43.  
  44.   map<int,int> last;
  45.  
  46.   int R = 1;
  47.   for(int i = 0; i < m; ++i) {
  48.     int idx = q[i].first;
  49.     int l = q[i].second.first;
  50.     int r = q[i].second.second;
  51.  
  52.     while(R <= r) {
  53.       int x = a[R];
  54.  
  55.       auto f = last.find(x);
  56.  
  57.       if(f == last.end())
  58.         last[x] = R;
  59.       else
  60.         update(f->second, -1), f->second = R;
  61.  
  62.       update(R++, 1);
  63.     }
  64.  
  65.     ans[idx] = query(r) - query(l-1);
  66.   }
  67.  
  68.   for(int i = 0; i < m; ++i)
  69.     printf("%d\n", ans[i]);
  70. }
Success #stdin #stdout 0s 7828KB
comments (?)
stdin
copy 
5
1 1 2 1 3
3
1 5
2 4
3 5
stdout
copy 
3
2
3
https://ideone.com/SBjZqI
problem DQUERY, based on SPOJ submission 17665944 (C++14), 2016-09-07 14:18:17
language:
C++14 (gcc 8.3)
created:
7 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!