1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cmath> 5 #include <cstring> 6 #include <queue> 7 #include <set> 8 #include <vector> 9 #include <map>10 #define ll long long11 12 using namespace std;13 14 const int N=30000+7;15 const int M=1000000+7;16 17 int Ls[N*20],Rs[N*20],sum[N*20],root[N];18 int tot=0;19 20 int pos[M];21 int a[N];22 int n,q;23 24 inline void copy(int x,int y){25     Ls[x]=Ls[y];26     Rs[x]=Rs[y];27     sum[x]=sum[y];28 }29 30 inline int bulidtree(int L,int R){31     if (L>R) return 0;32     int k=tot++;33     sum[k]=0;34     if (L==R) return k;35     int mid=(L+R)>>1;36     Ls[k]=bulidtree(L,mid);37     Rs[k]=bulidtree(mid+1,R);38     return k;39 }    40 41 inline int update(int o,int p,int v,int L,int R){42     int k=tot++;43     copy(k,o);44     sum[k]+=v;45 46     if (L==R) return k;47     48     int mid=(L+R)>>1;49     if (p<=mid) Ls[k]=update(Ls[k],p,v,L,mid);50     else Rs[k]=update(Rs[k],p,v,mid+1,R);51 52     return k;53 }54 55 inline int query(int o,int x,int y,int L,int R){56     if (L==x && R==y) return sum[o];57     int mid=(L+R)>>1;58     if (y<=mid) return query(Ls[o],x,y,L,mid);59     else if (x>mid) return query(Rs[o],x,y,mid+1,R);60     else return query(Ls[o],x,mid,L,mid)+query(Rs[o],mid+1,y,mid+1,R);61 }62 63 int main(){64     scanf("%d",&n);65     for (int i=1;i<=n;i++) scanf("%d",a+i);66 67     root[0]=bulidtree(1,n);68 69     memset(pos,-1,sizeof(pos));70     for (int i=1;i<=n;i++){71         root[i]=root[i-1];72         if (~pos[a[i]]) 73             root[i]=update(root[i],pos[a[i]],-1,1,n);74         root[i]=update(root[i],i,1,1,n);75         pos[a[i]]=i;76     }77 78     scanf("%d",&q);79     int x,y;80     while (q--){81         scanf("%d %d",&x, &y);82         printf("%d\n",query(root[y],x,y,1,n));83     }84 85     return 0;86 }

 1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cmath> 5 #include <cstring> 6 #include <queue> 7 #include <set> 8 #include <vector> 9 #include <map>10 #define ll long long11 12 using namespace std;13 14 const int N=30007;15 const int Q=200007;16 const int M=1000007;17 18 struct query{19     int L,R;20     int id;21     bool operator < (const query & t) const {22         return R<t.R;23     }24 }q[Q];25 26 int a[N];27 int pos[M]={};28 int ans[Q];29 30 int c[N]; // 树状数组31 int n;32 33 inline int lowbit(int x){34     return x&(-x);35 }36 37 inline void add(int x,int d){38     while (x<=n) {39         c[x]+=d;40         x+=lowbit(x);41     }42 }43 44 inline int sum(int x){45     int ret=0;46     while (x){47         ret+=c[x];48         x-=lowbit(x);49     }50     return ret;51 }52 53 int main(){54     scanf("%d",&n);55     for (int i=1;i<=n;i++) scanf("%d",a+i);56 57     int m;58     scanf("%d",&m);59     for (int i=1;i<=m;i++) scanf("%d %d",&q[i].L, &q[i].R),q[i].id=i;60     sort(q+1,q+1+m);61     62     int j=1;63     for (int i=1;i<=n;i++){64         if (pos[a[i]]) add(pos[a[i]],-1);65         add(i,1);66         pos[a[i]]=i;67 68         while (j<=m && q[j].R==i){69             ans[q[j].id]=sum(q[j].R)-sum(q[j].L-1);70             j++;71         }72     }73 74     for (int i=1;i<=m;i++) printf("%d\n",ans[i]);75 76     return 0;77 }