fork(16) download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int maxn = 1e5, maxk = 1e6 + 1;
  6. int root[maxn], L[16 * maxn], R[16 * maxn], sum[16 * maxn];
  7. int rt = 1, sz = 1;
  8. int lpos[maxk];
  9.  
  10. int copy(int v, int &u)
  11. {
  12. L[sz] = L[v];
  13. R[sz] = R[v];
  14. sum[sz] = sum[v];
  15. return u = sz++;
  16. }
  17.  
  18. void make_root()
  19. {
  20. copy(root[rt - 1], root[rt]);
  21. rt++;
  22. }
  23.  
  24. void add(int pos, int x, int v = root[rt - 1], int l = 0, int r = maxn)
  25. {
  26. sum[v] += x;
  27. if(r - l == 1)
  28. return;
  29. int m = (l + r) / 2;
  30. if(pos < m)
  31. add(pos, x, copy(L[v], L[v]), l, m);
  32. else
  33. add(pos, x, copy(R[v], R[v]), m, r);
  34. }
  35.  
  36. int get(int a, int b, int v, int l = 0, int r = maxn)
  37. {
  38. if(a <= l && r <= b)
  39. return sum[v];
  40. if(r <= a || b <= l)
  41. return 0;
  42. int m = (l + r) / 2;
  43. return get(a, b, L[v], l, m) + get(a, b, R[v], m, r);
  44. }
  45.  
  46. int main()
  47. {
  48. ios::sync_with_stdio(0);
  49. cin.tie(0);
  50. int n;
  51. cin >> n;
  52. for(int i = 1; i <= n; i++)
  53. {
  54. int t;
  55. cin >> t;
  56. make_root();
  57. add(lpos[t], -1);
  58. lpos[t] = i;
  59. add(lpos[t], 1);
  60. }
  61.  
  62. int q, l, r;
  63. cin >> q;
  64. while(q--)
  65. {
  66. cin >> l >> r;
  67. cout << get(l, r + 1, root[r]) << "\n";
  68. }
  69. return 0;
  70. }
  71.  
Success #stdin #stdout 0s 26280KB
stdin
5
1 1 2 1 3
3
1 5
2 4
3 5
stdout
3
2
3