预处理出每一个点下一个相同颜色的位置，记为next，然后将询问按左端点排序后不断右移左指针，设要删除i位置，就令f[next[next[i]]+1，同时还要删除原来的标记，即令f[next[i]]-1，最后即询问$\sum_{i=1}^{r}f[i]$，线段树维护即可。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 2000005 4 #define L (k<<1) 5 #define R (L+1) 6 #define mid (l+r>>1) 7 struct ji{ 8 int x,y,id; 9 bool operator < (const ji &a)const{ 10 return x<a.x; 11 } 12 }q[N]; 13 int n,m,l,ans[N],a[N],fi[N],nex[N],f[N<<2]; 14 void update(int k,int l,int r,int x,int y){ 15 if (l==r){ 16 f[k]+=y; 17 return; 18 } 19 if (x<=mid)update(L,l,mid,x,y); 20 else update(R,mid+1,r,x,y); 21 f[k]=f[L]+f[R]; 22 } 23 int query(int k,int l,int r,int x,int y){ 24 if ((l>y)||(x>r))return 0; 25 if ((x<=l)&&(r<=y))return f[k]; 26 return query(L,l,mid,x,y)+query(R,mid+1,r,x,y); 27 } 28 int main(){ 29 scanf("%d%*d%d",&n,&m); 30 for(int i=1;i<=n;i++)scanf("%d",&a[i]); 31 for(int i=n;i;i--){ 32 nex[i]=fi[a[i]]; 33 fi[a[i]]=i; 34 } 35 for(int i=1;i<N-4;i++) 36 if (nex[fi[i]])update(1,1,n,nex[fi[i]],1); 37 for(int i=1;i<=m;i++){ 38 scanf("%d%d",&q[i].x,&q[i].y); 39 q[i].id=i; 40 } 41 sort(q+1,q+m+1); 42 l=1; 43 for(int i=1;i<=m;i++){ 44 while (l<q[i].x){ 45 if (nex[l])update(1,1,n,nex[l],-1); 46 if (nex[nex[l]])update(1,1,n,nex[nex[l]],1); 47 l++; 48 } 49 ans[q[i].id]=query(1,1,n,q[i].x,q[i].y); 50 } 51 for(int i=1;i<=m;i++)printf("%d\n",ans[i]); 52 }