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

离线 + 树状数组维护

1 #include
      
        2   3 using namespace std; 4  5 const int MAXN = 2333666; 6 int n, a[MAXN], start[MAXN], nex[MAXN], q, t[MAXN], an[MAXN], k[MAXN]; 7 pair
       
         Q[MAXN]; 8  9 template 
        
          void read (tn & a) {10     tn x = 0, f = 1;11     char c = getchar();12     while (c < '0' || c > '9'){ if (c == '-') f = -1; c = getchar(); }13     while (c >= '0' && c <= '9'){ x = x * 10 + c - '0'; c = getchar(); }14     a = f == 1 ? x : -x;15 }16 17 void add (int k, int d) {18     while (k <= n) {19         t[k] += d;20         k += k & -k;21     }22 }23 24 int sum (int k) {25     int s = 0;26     while (k > 0) {27         s += t[k];28         k -= k & -k;29     }30     return s;31 }32 33 bool cmp (const int &i, const int & j) {34     return Q[i] < Q[j];35 }36 37 int main() {38     read(n);39     for (int i = 1; i <= n; ++i) {40         read(a[i]);41     }42     for (int i = n; i >= 1; --i) {43         if (start[a[i]] != 0) add(start[a[i]], -1);44         add(i, 1);45         nex[i] = start[a[i]];46         start[a[i]] = i;47     }48     read(q);49     for (int i = 1; i <= q; ++i) {50         read(Q[i].first);51         read(Q[i].second);52     }53     for (int i = 1; i <= q; ++i) k[i] = i;54     sort(k + 1, k + 1 + q, cmp);55     int lx = 1;56     for (int i = 1; i <= q; ++i) {57         while (Q[k[i]].first > lx) {58             if (sum(lx) - sum(lx - 1) > 0) {59                 if (nex[lx] != 0) add(nex[lx], 1);60                 add(lx, -1);61             }62             ++lx;63         }64         an[k[i]] = sum(Q[k[i]].second) - sum(Q[k[i]].first - 1);65     }66     for (int i = 1; i <= q; ++i) printf("%d ", an[i]); printf("\n");67     return 0;68 }