fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define fou(i,a,b) for (int i = a; i <= b; i++)
  3. #define fod(i,a,b) for (int i = a; i >= b; i--)
  4.  
  5. #define pb push_back
  6.  
  7. using namespace std;
  8.  
  9. const int N = 3*1e6+5;
  10.  
  11. struct Query {int l, id;};
  12.  
  13. int n, numQ;
  14.  
  15. int a[N];
  16.  
  17. vector<Query> q[N];
  18.  
  19. map<int,int> trace;
  20.  
  21. int st[N];
  22.  
  23. void update(int id, int l, int r, int pos, int val)
  24. {
  25.     if (l == r) return void(st[id] = val);
  26.     int m = l + (r-l)/2;
  27.     if (pos <= m) update(2*id,l,m,pos,val);
  28.     else update(2*id+1,m+1,r,pos,val);
  29.     st[id] = st[2*id] + st[2*id+1];
  30. }
  31.  
  32. int get(int id, int l, int r, int s, int e)
  33. {
  34.     if (l > e || r < s) return 0;
  35.     if (s <= l && r <= e) return st[id];
  36.     int m = l + (r-l)/2;
  37.     return get(2*id,l,m,s,e) + get(2*id+1,m+1,r,s,e);
  38. }
  39.  
  40. int ans[N];
  41.  
  42. signed main() {
  43.     ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  44.     cin >> n;
  45.     fou(i,1,n) cin >> a[i];
  46.     cin >> numQ;
  47.     fou(i,1,numQ)
  48.     {
  49.         int l,r;
  50.         cin >> l >> r;
  51.         q[r].pb({l,i});
  52.     }
  53.     fou(i,1,n)
  54.     {
  55.         if (trace[a[i]]) update(1,1,n,trace[a[i]],0);
  56.         update(1,1,n,i,1);
  57.         trace[a[i]] = i;
  58.         for (auto r:q[i]) ans[r.id] = get(1,1,n,r.l,i);
  59.     }
  60.     fou(i,1,numQ) cout << ans[i] << endl;
  61.     return 0;
  62.  
  63. }
  64.  
Success #stdin #stdout 0.01s 5256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rzpWjc
language:
C++14 (gcc 8.3)
created:
70 days 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!