分析：
做这个题还是需要技巧的。
先将所有查询读入，按照右端点排序。
从1~n扫，维护pt[i]表示i向左第一个和a[i]相等的数字的位置，扫到i的时候实时更新树状数组：c[pt[pt[i]]+1]~c[pt[i]]区间+1（pt[i]!=0），与此同时，处理右端点与i重合的查询，此询问的答案就是这个询问的左端点在树状数组中的值（树状数组起区间修改单点查询的功能），至于为什么，画个图应该很容易知道。
PS:树状数组的区间修改单点查询的实现：
将原数组差分，令d[i]=c[i]-c[i-1]，特别地，d[1]=c[1]。
那么区间[l,r]整体加上k的操作就可以简单地使用d[l]+=k;d[r+1]-=k来完成了。
此时c[n]=sigma(d[i]) 1<=i<=n，所以单点查询c[n]实际上就是在求d数组的[1~n]区间和。
View Code
1 #include <cstdlib> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 #include <algorithm> 6 7 using namespace std; 8 9 #define lowbit(x) (x&(-x)) 10 #define N 2100000 11 12 struct ASK 13 { 14 int l,r,p; 15 }ask[N]; 16 17 int c[N],n,qu,lim,a[N],pt[N],pre[N],ans[N]; 18 19 inline bool cmp(const ASK &a,const ASK &b) 20 { 21 return a.r<b.r; 22 } 23 24 void updata(int x,int dt) 25 { 26 while(x<=n) 27 { 28 c[x]+=dt; 29 x+=lowbit(x); 30 } 31 } 32 33 int getsum(int x) 34 { 35 int rt=0; 36 while(x) 37 { 38 rt+=c[x]; 39 x-=lowbit(x); 40 } 41 return rt; 42 } 43 44 void read() 45 { 46 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 47 for(int i=1;i<=qu;i++) 48 { 49 scanf("%d%d",&ask[i].l,&ask[i].r); 50 ask[i].p=i; 51 } 52 sort(ask+1,ask+1+qu,cmp); 53 } 54 55 void modify(int x) 56 { 57 pt[x]=pre[a[x]]; 58 pre[a[x]]=x; 59 if(pt[x]!=0) 60 { 61 updata(pt[pt[x]]+1,1); 62 updata(pt[x]+1,-1); 63 } 64 } 65 66 void go() 67 { 68 int head=1; 69 for(int i=1;i<=n;i++) 70 { 71 modify(i); 72 while(ask[head].r==i) 73 { 74 ans[ask[head].p]=getsum(ask[head].l); 75 head++; 76 } 77 } 78 for(int i=1;i<=qu;i++) printf("%d\n",ans[i]); 79 } 80 81 int main() 82 { 83 while(scanf("%d%d%d",&n,&lim,&qu)!=EOF) 84 { 85 read(); 86 go(); 87 } 88 return 0; 89 }