fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int const N = 30 * 1000 + 16;
  6.  
  7. int n, m;
  8. int a[N], b[N], last[N];
  9.  
  10. struct tree {
  11.   int v;
  12.   tree *lf, *rg;
  13.  
  14.   tree(tree* tmp) {
  15.     *this = *tmp;
  16.   }
  17.  
  18.   tree(int l, int r) {
  19.     v = 0;
  20.     if(l == r)
  21.       return;
  22.     int m = l + r >> 1;
  23.     lf = new tree(l, m);
  24.     rg = new tree(m+1, r);
  25.   }
  26.  
  27.   int query(int l, int r, int L, int R) {
  28.     if(L <= l && r <= R)
  29.       return v;
  30.     int m = l + r >> 1;
  31.     if(R <= m)
  32.       return lf->query(l, m, L, R);
  33.     else if(m < L)
  34.       return rg->query(m+1, r, L, R);
  35.     else
  36.       return lf->query(l, m, L, m) + rg->query(m+1, r, m+1, R);
  37.   }
  38.  
  39.   tree* update(int l, int r, int i, int v) {
  40.     auto tmp = new tree(this);
  41.     if(l == i && i == r) {
  42.       tmp->v = v;
  43.     } else {
  44.       int m = l+r>>1;
  45.       if(i <= m)
  46.         tmp->lf = lf->update(l, m, i, v);
  47.       else
  48.         tmp->rg = rg->update(m+1, r, i, v);
  49.       tmp->v = tmp->lf->v + tmp->rg->v;
  50.     }    
  51.     return tmp;
  52.   }
  53. };
  54.  
  55. tree* ver[N];
  56.  
  57. int main()
  58. {
  59.   scanf("%d", &n);
  60.   for(int i = 1; i <= n; ++i) {
  61.     int x;
  62.     scanf("%d", &x);
  63.     a[i] = b[i-1] = x;
  64.   }
  65.   sort(b, b+n);
  66.   m = unique(b, b+n) - b;
  67.  
  68.   ver[0] = new tree(1, n);
  69.  
  70.   for(int i = 1; i <= n; ++i) {
  71.     int x = lower_bound(b, b+m, a[i]) - b;
  72.     auto old = ver[i-1];
  73.     if(last[x])
  74.       old = old->update(1, n, last[x], 0);
  75.     ver[i] = old->update(1, n, i, 1);
  76.     last[x] = i;
  77.   }
  78.  
  79.   int q;
  80.   scanf("%d", &q);
  81.   while(q--) {
  82.     int l, r;
  83.     scanf("%d%d", &l, &r);
  84.     printf("%d\n", ver[r]->query(1, n, l, r));
  85.   }
  86. }
Success #stdin #stdout 0s 3956KB
comments (?)
stdin
copy 
5
1 1 2 1 3
3
1 5
2 4
3 5
stdout
copy 
3
2
3
https://ideone.com/98mZhB
problem DQUERY, based on SPOJ submission 18655339 (C++14), 2017-01-28 00:02:45
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!