fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define up(i,a,b) for (int i = (int)a; i <= (int)b; i++)
  3. #define ep emplace_back
  4. using namespace std;
  5.  
  6. const int maxn = 2e5 + 10;
  7. const int LOG = log2(maxn)+2;
  8. struct Node{
  9.     int l = 0, r = 0;
  10.     int sum = 0;
  11. };
  12. Node T[maxn*LOG];
  13.  
  14. int n,q;
  15. int cnt = 0;
  16. int ROOT[maxn];
  17. int a[maxn];
  18.  
  19. void build(int& nod, int l, int r){
  20.     nod = ++cnt;
  21.     if (l == r){
  22.         T[nod].sum = 0;
  23.         return;
  24.     }
  25.     int mid = (l+r) >> 1;
  26.     build(T[nod].l, l, mid);
  27.     build(T[nod].r, mid+1, r);
  28. }
  29.  
  30. void push_up(int nod){
  31.     T[nod].sum = T[T[nod].l].sum + T[T[nod].r].sum;
  32. }
  33.  
  34. void update(int& nod, int prev_nod, int l, int r, int pos, int val){
  35.     nod = ++cnt;
  36.     T[nod] = T[prev_nod];
  37.     if (l == r){
  38.         T[nod].sum += val;
  39.         return;
  40.     }
  41.  
  42.     int mid = (l+r) >> 1;
  43.     if (pos <= mid) update(T[nod].l, T[prev_nod].l, l, mid, pos, val);
  44.     else update(T[nod].r, T[prev_nod].r, mid+1, r, pos, val);
  45.     push_up(nod);
  46. }
  47.  
  48. int query(int nod, int l, int r, int u, int v){
  49.     if (l > v || r < u) return 0;
  50.     if (l >= u && r <= v) return T[nod].sum;
  51.     int mid = (l+r) >> 1;
  52.     int L = query(T[nod].l, l, mid, u, v);
  53.     int R = query(T[nod].r, mid+1, r, u, v);
  54.     return L+R;
  55. }
  56.  
  57. int pre[1000001];
  58. signed main(){
  59.     ios_base::sync_with_stdio(false);
  60.     cin.tie(0);
  61.     #define Task "A"
  62.     if (fopen(Task".inp", "r")){
  63.         freopen(Task".inp", "r", stdin);
  64.         freopen(Task".out", "w", stdout);
  65.     }
  66.  
  67.     cin >> n;
  68.     up(i,1,n) cin >> a[i];
  69.     build(ROOT[0], 1, n);
  70.  
  71.     up(i,1,n){
  72.         if (pre[a[i]]){
  73.             update(ROOT[i], ROOT[i-1], 1, n, pre[a[i]], -1);
  74.             update(ROOT[i], ROOT[i], 1, n, i, 1);
  75.         }
  76.         else{
  77.             update(ROOT[i], ROOT[i-1], 1, n, i, 1);
  78.         }
  79.         pre[a[i]] = i;
  80.     }
  81.  
  82.     cin >> q;
  83.     while (q--){
  84.         int l, r;
  85.         cin >> l >> r;
  86.         cout << query(ROOT[r], 1, n, l, r) << "\n";
  87.     }
  88. }
  89.  
  90.  
Success #stdin #stdout 0.01s 7696KB
comments (?)
stdin
copy 
5
10 13 3 13 11
3
2 3
2 4
3 5
stdout
copy 
2
2
3
https://ideone.com/qlu6x0
language:
C++14 (gcc 8.3)
created:
2 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!