离线不同数

 1 int s[N],a[N];//离线瞎搞 
 2 int n,q,ans[M];
 3 int nxt[N];
 4 map<int,int >mp;
 5 struct Question{
 6     int l,r,id;
 7     bool operator<(const Question q)const{
 8         return l<q.l;
 9     }
10 }Q[M];
11 void add(int x,int val){
12     for(int i=x;i<=n;i+=lowbit(i)) s[i]+=val;
13 }
14 int query(int x){
15     int ret=0;
16     for(int i=x;i>0;i-=lowbit(i))
17         ret+=s[i];
18     return ret;
19 }
20 int main(){
21     while(scanf("%d",&n)!=EOF){
22         mp.clear();
23         for(int i=1;i<=n;i++){
24             scanf("%d",&a[i]);
25             if(mp.find(a[i])==mp.end()){
26                 mp[a[i]]=i;
27                 add(i,1);
28             }
29         }
30         mp.clear();
31         for(int i=n;i;i--){
32             if(mp.find(a[i])==mp.end())
33                 nxt[i]=n+1;
34             else
35                 nxt[i]=mp[a[i]];
36             mp[a[i]]=i;
37         }
38         scanf("%d",&q);
39         for(int i=0;i<q;i++){
40             scanf("%d%d",&Q[i].l,&Q[i].r);
41             Q[i].id=i;
42         }
43         sort(Q,Q+q);
44         int t=1;
45         for(int i=0;i<q;i++){
46             while(t<=n&&t<Q[i].l)
47                 add(nxt[t++],1);
48             ans[Q[i].id]=query(Q[i].r)-query(Q[i].l-1);
49         }
50         for(int i=0;i<q;i++)
51             printf("%d
",ans[i]);
52     }
53     return 0;
54 }