传送门 题解：用主席树维护区间内不相同的数，将重复的元素建树，进行query( )的时候，用区间长度(r-l+1)相减就是答案。 注意：query( )的写法要注意，不是对称查找！！！
#include<bits/stdc++.h> using namespace std; #define lson lc[rt],l,mid #define rson rc[rt],mid+1,r const int MAXN=5e4+2; int n,m; int tim=0,a[MAXN],sum[MAXN*20],lc[MAXN*20],rc[MAXN*20],root[MAXN]; inline int read() { int x=0;char c=getchar(); while (c<'0'||c>'9') c=getchar(); while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x; } void build(int rt,int l,int r) { rt=++tim; sum[rt]=0; if (l==r) return ; int mid=(l+r)>>1; build(lson); build(rson); } void Insert(int &rt,int pre,int l,int r,int x) { rt=++tim; sum[rt]=sum[pre]+1; if (l==r) return ; lc[rt]=lc[pre],rc[rt]=rc[pre]; int mid=(l+r)>>1; if (x<=mid) Insert(lc[rt],lc[pre],l,mid,x); else Insert(rc[rt],rc[pre],mid+1,r,x); } int query(int s,int t,int l,int r,int x) { if (l>=x) return sum[t]-sum[s]; int mid=(l+r)>>1,ans=0; if (x<=mid) ans+=query(lc[s],lc[t],l,mid,x); ans+=query(rc[s],rc[t],mid+1,r,x); return ans; } int main() { // freopen("P1972.in","r",stdin); n=read(); for (register int i=1;i<=n;++i) a[i]=read(); build(root[0],1,n); map<int,int > mp; mp.clear(); for (register int i=1;i<=n;++i) { if (mp.find(a[i])==mp.end()) root[i]=root[i-1]; else Insert(root[i],root[i-1],1,n,mp[a[i]]); mp[a[i]]=i; } m=read(); for (register int i=1;i<=m;++i) { int l=read(),r=read(); printf("%d\n",r-l+1-query(root[l-1],root[r],1,n,l)); } return 0; }