本文共 1675 字，大约阅读时间需要 5 分钟。
题意：
给一个序列，问区间内有多少个不相同的数
思路：
主席树模版，按斌巨的模版写了一发orz
/* ***********************************************Author :devil************************************************ */#include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int mod=1e9+7;const int N=3e4+10;const int M=N*100;int n,q,tot,x,y;int a[N],T[N],ls[M],rs[M],c[M];int build(int l,int r){ int node=tot++; c[node]=0; if(l!=r) { int mid=(l+r)>>1; ls[node]=build(l,mid); rs[node]=build(mid+1,r); } return node;}int update(int node,int pos,int val){ int newnode=tot++,tmp=newnode; c[newnode]=c[node]+val; int l=1,r=n; while(l >1; if(pos<=mid) { ls[newnode]=tot++; rs[newnode]=rs[node]; newnode=ls[newnode]; node=ls[node]; r=mid; } else { rs[newnode]=tot++; ls[newnode]=ls[node]; newnode=rs[newnode]; node=rs[node]; l=mid+1; } c[newnode]=c[node]+val; } return tmp;}int query(int node,int pos){ int ret=0,l=1,r=n; while(pos >1; if(pos<=mid) { r=mid; node=ls[node]; } else { ret+=c[ls[node]]; node=rs[node]; l=mid+1; } } return ret+c[node];}int main(){ //freopen("in.txt","r",stdin); while(~scanf("%d",&n)) { tot=0; for(int i=1;i<=n;i++) scanf("%d",&a[i]); T[n+1]=build(1,n); map mp; for(int i=n;i>=1;i--) { if(mp.find(a[i])==mp.end()) T[i]=update(T[i+1],i,1); else { int tmp=update(T[i+1],mp[a[i]],-1); T[i]=update(tmp,i,1); } mp[a[i]]=i; } scanf("%d",&q); while(q--) { scanf("%d%d",&x,&y); printf("%d\n",query(T[x],y)); } } return 0;}
转载于:https://www.cnblogs.com/d-e-v-i-l/p/5765369.html