题目链接：https://vjudge.net/problem/SPOJ-DQUERY

题意：给定数列，q次询问，问区间内不同数字的个数。

可以用主席树，但是还有更好写的办法。

离线存下所有的询问，按照询问右端点从小到大排序。

用树状数组标记“某个值在区间[1,r]中出现的最后的位置”。这样可以将r从左向右平移，每一个r更新所有右边界为r的查询。

因为某值出现总是尽可能向后，所以这样可以保证可以被查到。

用一个map来记录某个值出现的位置，然后移动的时候更新树状数组就行了。整体复杂度就是O(n*logn+Q)的。

 

1 #include 
     
       2 using namespace std; 3  4 typedef struct Event { 5     int l, r, id; 6 }Event; 7 const int maxn = 200100; 8 int n, q, a[maxn]; 9 int bit[maxn];10 vector
      
        event;11 int ret[maxn];12 unordered_map
       
         vis;13 14 bool cmp(Event a, Event b) { return a.r < b.r; }15 int lowbit(int x) { return x & (-x); }16 void add(int i, int v) { for(; i <= n; i+=lowbit(i)) bit[i] += v; }17 int sum(int i) { int ret = 0; for(; i > 0; i-=lowbit(i)) ret += bit[i]; return ret; }18 19 int main() {20     // freopen("in", "r", stdin);21     int l, r;22     while(~scanf("%d",&n)) {23         for(int i = 1; i <= n; i++) scanf("%d", &a[i]);24         event.clear(); vis.clear();25         memset(bit, 0, sizeof(bit));26         scanf("%d", &q);27         for(int i = 1; i <= q; i++) {28             scanf("%d%d",&l,&r);29             event.push_back(Event{l,r,i});30         }31         sort(event.begin(), event.end(), cmp);32         r = 0;33         for(int i = 1; i <= n; i++) {34             if(vis.find(a[i]) == vis.end()) {35                 vis[a[i]] = i;36                 add(i, 1);37             }38             else {39                 add(vis[a[i]], -1);40                 vis[a[i]] = i;41                 add(i, 1);42             }43             while(event[r].r == i) {44                 ret[event[r].id] = sum(event[r].r) - sum(event[r].l-1);45                 r++;46             }47         }48         for(int i = 1; i <= q; i++) printf("%d\n", ret[i]);49     }50     return 0;51 }