原题链接
题意：
求区间内不同元素的个数。
思路：
应该也能用主席树（如果我会.jpg）
对于一段区间来说，每个元素出现的有效位置是最右边的位置。
比如 1 2 3 4 1来说,当查询[i,5]区间时，1位置上的1是无用的，所以对于每个数只需要维护在某区间里最右的位置即可。
将所有询问存储下来，按照r排序，用树状数组维护一下1～i里有多少个不同的数字，答案就是qask (r )-qask(l-1);记录每个元素在当前询问区间里出现的最右端的位置，如果说该元素重新出现的话，就将上一次出现的位置的贡献减去，再加上本次位置的贡献。
代码：
#pragma GCC optimize(3) ///#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") #pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll>PLL; typedef pair<int,int>PII; typedef pair<double,double>PDD; #define I_int ll inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); //cout<<" "; } ll ksm(ll a,ll b,ll p) { ll res=1; while(b) { if(b&1)res=res*a%p; a=a*a%p; b>>=1; } return res; } const int inf=0x3f3f3f3f,mod=998244353; const ll INF = 0x3f3f3f3f3f3f3f3f; const int maxn=2e6+100,maxm=3e5+7,N=1e6+7; const double PI = atan(1.0)*4; int a[maxn],n,m; struct node{ int l,r; int pos; }q[maxn]; int vis[maxn],las; int res[maxn]; bool cmp(node a,node b){ return a.r<b.r; } int tr[maxn]; int lowbit(int x){ return x&-x; } void update(int pos,int val){ while(pos<=n) tr[pos]+=val,pos+=lowbit(pos); } int qask(int pos){ int res=0; while(pos) res+=tr[pos],pos-=lowbit(pos); return res; } int main(){ n=read(); for(int i=1;i<=n;i++) a[i]=read(); m=read(); for(int i=1;i<=m;i++){ q[i].l=read(),q[i].r=read(); q[i].pos=i; } sort(q+1,q+1+m,cmp); int last=1; for(int i=1;i<=m;i++){ for(int j=last;j<=q[i].r;j++){ if(vis[a[j]]) update(vis[a[j]],-1); vis[a[j]]=j; update(j,1); } last=q[i].r+1; res[q[i].pos]=qask(q[i].r)-qask(q[i].l-1); } for(int i=1;i<=m;i++) printf("%d\n",res[i]); return 0; }
