一道简单题。
不用可持久化。
对于统计颜色个数，可以看与其颜色一样的前一个位置。
设$las(i)$表示其与$i$颜色相等的上一个位置。
则对于二元组$(l,r)$，其答案为$sum_{i=l}^{r} las(i)<=l-1$。
可持久化强上即可。
若不用的话可以讲$(l,r)$拆成两个操作，然后对于其排序即可，每次维护从$[1,x]$中小于等于$l-1$的和，然后就每次动态加点，查询，省略了其可持久化的过程。
所以做两次树状数组，但是因为树状数组不能有$0$所以需要$+1$。
离散化方便寻找$las(i)$，不需要链表什么的。
时间复杂度：$O(nlog n)$
正确性显然。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; inline int read(){ int f=1,ans=0;char c=getchar(); while(c<'0'|c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return f*ans; } const int MAXN=500001; int n,a[MAXN],m,tot,tmp[MAXN],M[MAXN],las[MAXN],Ans[MAXN]; struct BIT{ int c[MAXN]; inline int lowbit(int x){return x&-x;} inline void add(int x){ for(;x<=n;x+=lowbit(x)) c[x]++; return; } inline int qsum(int x){ int res=0; for(;x;x-=lowbit(x)) res+=c[x]; return res; } inline void clear(){memset(c,0,sizeof(c));return;} }bit; struct Query{ int pos,opt,k,id; }query[MAXN<<1]; bool cmp(Query x1,Query x2){ if(x1.opt==x2.opt) return x1.pos<x2.pos; return x1.opt<x2.opt; } int main(){ // freopen("5.in","r",stdin); n=read(); for(int i=1;i<=n;i++) a[i]=tmp[++tmp[0]]=read(); sort(tmp+1,tmp+n+1); for(int i=1;i<=n;i++) a[i]=lower_bound(tmp+1,tmp+n+1,a[i])-tmp; for(int i=1;i<=n;i++) las[i]=M[a[i]]+1,M[a[i]]=i; m=read(); for(int i=1;i<=m;i++){ int l=read(),r=read(); query[++tot].pos=l-1,query[tot].opt=-1,query[tot].k=l,query[tot].id=i; query[++tot].pos=r,query[tot].opt=1;query[tot].k=l,query[tot].id=i; } sort(query+1,query+tot+1,cmp); int l=1,r=m+1;bit.clear(); while(query[l].pos==0&&l<=m) l++; while(query[r].pos==0&&r<=2*m) r++; for(int i=1;i<=n;++i){ bit.add(las[i]); while(l<=m&&query[l].pos==i) Ans[query[l].id]-=bit.qsum(query[l].k),++l; while(r<=2*m&&query[r].pos==i) Ans[query[r].id]+=bit.qsum(query[r].k),++r; } for(int i=1;i<=m;i++) printf("%d ",Ans[i]); return 0; }