SPOJ3276 D-query

题意：n个数 a...a，q组询问，每组询问给定 l，r，输出 [ l, r ] 有多少不同的数 ( n ≤30000, q ≤200000, a ≤ 10)

离线 + 树状数组维护

 #include<bits/stdc++.h>

 using namespace std;

 const int MAXN = ;

 int n, a[MAXN], start[MAXN], nex[MAXN], q, t[MAXN], an[MAXN], k[MAXN];

 pair<int, int> Q[MAXN];

 template <typename tn> void read (tn & a) {

     tn x = , f = ;

     char c = getchar();

     while (c < '' || c > ''){ if (c == '-') f = -; c = getchar(); }

     while (c >= '' && c <= ''){ x = x *  + c - ''; c = getchar(); }

     a = f ==  ? x : -x;

 }

 void add (int k, int d) {

     while (k <= n) {

         t[k] += d;

         k += k & -k;

     }

 }

 int sum (int k) {

     int s = ;

     while (k > ) {

         s += t[k];

         k -= k & -k;

     }

     return s;

 }

 bool cmp (const int &i, const int & j) {

     return Q[i] < Q[j];

 }

 int main() {

     read(n);

     for (int i = ; i <= n; ++i) {

         read(a[i]);

     }

     for (int i = n; i >= ; --i) {

         if (start[a[i]] != ) add(start[a[i]], -);

         add(i, );

         nex[i] = start[a[i]];

         start[a[i]] = i;

     }

     read(q);

     for (int i = ; i <= q; ++i) {

         read(Q[i].first);

         read(Q[i].second);

     }

     for (int i = ; i <= q; ++i) k[i] = i;

     sort(k + , k +  + q, cmp);

     int lx = ;

     for (int i = ; i <= q; ++i) {

         while (Q[k[i]].first > lx) {

             if (sum(lx) - sum(lx - ) > ) {

                 if (nex[lx] != ) add(nex[lx], );

                 add(lx, -);

             }

             ++lx;

         }

         an[k[i]] = sum(Q[k[i]].second) - sum(Q[k[i]].first - );

     }

     for (int i = ; i <= q; ++i) printf("%d ", an[i]); printf("\n");

     return ;

 }