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