fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty