fork download
copy 
  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.  }
Runtime error #stdin #stdout 0s 26456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5xMHRD
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!