由于昨天A组T2考了一道相似的题目，特来学习该题解法。
传送门：GO
对于给定询问，我们发现一些区间内相同的数字，只有一个做出贡献，拿题解中的一句话：
对于若干个询问的区间[l,r]，如果他们的r都相等的话，那么项链中出现的同一个数字，一定是只关心出现在最右边的那一个的
所以将询问区间按右端点排序，记录询问编号，根据数字的出现先后用树状数组处理状态，出现重复数字就将多余贡献删除并更新出现位置，当更新完右端点所在的点的状态时，记录此时答案。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int read(){ 4 int x=0,f=1; 5 char c=getchar(); 6 while(!isdigit(c)){ 7 if(c==‘-‘) f=-1; 8 c=getchar(); 9 } 10 while(isdigit(c)){ 11 x=(x<<1)+(x<<3)+(c^48); 12 c=getchar(); 13 } 14 return x*f; 15 } 16 const int N=1e6+10; 17 int n,m; 18 struct tree{ 19 int s[N]; 20 int lb(int o){return o&-o;} 21 void add(int o,int t){for(;o<=n;o+=lb(o))s[o]+=t;} 22 int query(int o){int ans=0;for(;o;o-=lb(o)) ans+=s[o];return ans;} 23 }a; 24 int ma[N]; 25 struct node{ 26 int l,r,pos; 27 bool operator < (const node &x)const{ 28 return r<x.r; 29 } 30 }que[N]; 31 int vis[N],ans[N]; 32 int main(){ 33 n=read(); 34 for(int i=1;i<=n;i++) ma[i]=read(); 35 m=read(); 36 for(int i=1;i<=m;i++){ 37 que[i].l=read(); 38 que[i].r=read(); 39 que[i].pos=i; 40 } 41 sort(que+1,que+m+1); 42 int pos=1; 43 for(int i=1;i<=m;i++){ 44 for(int j=pos;j<=que[i].r;j++){ 45 if(vis[ma[j]]) a.add(vis[ma[j]],-1); 46 a.add(j,1); 47 vis[ma[j]]=j; 48 } 49 pos=que[i].r+1; 50 ans[que[i].pos]=a.query(que[i].r)-a.query(que[i].l-1); 51 } 52 for(int i=1;i<=m;i++) printf("%d\n",ans[i]); 53 return 0; 54 }
原文：https://www.cnblogs.com/Nelson992770019/p/11796123.html