P1972 [SDOI2009] HH的项链

多次询问子序列 [L,R] 包含了多少种不同的数？

 把问题离线，按照R排序

ans[id] =qq(r)-qq(l-1)

但前面重复的要减去，比如（1，2，1，1）

#include <bits/stdc++.h>
using namespace std ;
 const int N=1e6+2,M=N*2;

struct T{
    int x,y,p;
}a[N] ;
 int sum[N] ,m,b[N],c[N],n,ans[N];
 
 int cmp(T &a,T &b){ return a.y<b.y; }
 
 int lowbit(int x){
     return x&-x;
 } 
 int qq(int x){
     int res= 0;
     for(;x;x-=lowbit(x)) res+=sum[x];
     return res; 
 }
 void add(int x,int v){
     for(;x<=n;x+=lowbit(x)) sum[x]+=v ;
 }
 
 signed main(){ 
     cin>>n;
     int i,j;
     for(i=1;i<=n;i++) cin>>c[i];
     cin>>m;
     for(i=1;i<=m;i++){
         cin>>a[i].x>>a[i].y; a[i].p=i;
     }
     sort(a+1,a+1+m,cmp);
     int nxt=1;
     for(i=1;i<=m;i++){
         for(j=nxt;j<=a[i].y;j++){
             if(b[c[j]]) add(b[c[j]],-1);
             add(j,1);
             b[c[j]]=j;
         }
         nxt=a[i].y+1;
         ans[a[i].p]= qq(a[i].y)-qq(a[i].x-1);
     }
     for(i=1;i<=m;i++) cout<<ans[i]<<'\n';
 }