https://vjudge.net/contest/311900#overview 树状数组+主席数
密码996996
先按r排序，然后每次清除该数前面已经出现的位置，增加它新出现的位置。然后查询。
#include<bits/stdc++.h> #define il inline #define pb push_back #define fi first #define se second #define ms(_data,v) memset(_data,v,sizeof(_data)) #define sc(n) scanf("%d",&n) #define SC(n,m) scanf("%d %d",&n,&m) #define SZ(a) int((a).size()) #define rep(i,a,b) for(int i=a;i<=b;++i) #define drep(i,a,b) for(int i=a;i>=b;--i) using namespace std; typedef long long ll; const ll inf=0x3f3f3f3f; const double PI=acos(-1.0); const double eps=1e-9; const int maxn=5e4+5; const int maxm=1e6+5; int a[maxn],sum[maxm],pre[maxm],ans[maxn<<2],n,m; struct node{ int l,r,id; }q[maxn<<2]; bool cmp(node x,node y){ return x.r<y.r; } void add(int p,int x){ while(p<=n) sum[p]+=x,p+=p&-p; } int ask(int p){ int res=0; while(p) res+=sum[p],p-=p&-p; return res; } int main(){ sc(n); rep(i,1,n) sc(a[i]); sc(m); rep(i,1,m){ SC(q[i].l,q[i].r); q[i].id=i; } sort(q+1,q+m+1,cmp); rep(i,1,m){ rep(j,q[i-1].r+1,q[i].r){ if(pre[a[j]]) add(pre[a[j]],-1); pre[a[j]]=j,add(pre[a[j]],1); } ans[q[i].id]=ask(q[i].r)-ask(q[i].l-1); } rep(i,1,m) printf("%d\n",ans[i]); return 0; }主席数模板题
#include<cstdio> #include<iostream> #include<algorithm> #include<string> #include<cstring> #include<queue> #include<stack> #include<map> #include<set> #include<cmath> #include<sstream> //#include<bits/stdc++.h> #define il inline #define pb push_back #define fi first #define se second #define ms(_data,v) memset(_data,v,sizeof(_data)) #define sc(n) scanf("%d",&n) #define SC(n,m) scanf("%d %d",&n,&m) #define SZ(a) int((a).size()) #define rep(i,a,b) for(int i=a;i<=b;++i) #define drep(i,a,b) for(int i=a;i>=b;--i) using namespace std; typedef long long ll; const ll inf=0x3f3f3f3f; const double PI=acos(-1.0); const double eps=1e-9; const int maxn=1e5+5; int a[maxn],b[maxn],rt[maxn*20],ls[maxn*20],rs[maxn*20],sum[maxn*20]; int n,m,tot; void build(int &rt,int l,int r){ rt=++tot; sum[rt]=0; if(l==r) return; int mid=(l+r)>>1; build(ls[rt],l,mid); build(rs[rt],mid+1,r); } void update(int &rt,int l,int r,int last,int p){ rt=++tot; ls[rt]=ls[last],rs[rt]=rs[last]; sum[rt]=sum[last]+1; if(l==r) return; int mid=(l+r)>>1; if(p<=mid) update(ls[rt],l,mid,ls[last],p); else update(rs[rt],mid+1,r,rs[last],p); } int query(int ss,int ee,int l,int r,int k){ if(l==r) return l; int mid=(l+r)>>1; int cnt=sum[ls[ee]]-sum[ls[ss]]; if(k<=cnt) return query(ls[ss],ls[ee],l,mid,k); else return query(rs[ss],rs[ee],mid+1,r,k-cnt); } int main(){ SC(n,m); rep(i,1,n) sc(a[i]),b[i]=a[i]; sort(b+1,b+n+1); int sz=unique(b+1,b+n+1)-(b+1); build(rt[0],1,sz); rep(i,1,n){ a[i]=lower_bound(b+1,b+sz+1,a[i])-b; update(rt[i],1,sz,rt[i-1],a[i]); } int l,r,k; rep(i,1,m){ sc(l),sc(r),sc(k); int id=query(rt[l-1],rt[r],1,sz,k); printf("%d\n",b[id]); } return 0; }待修改的主席数，俺也是才学。过了luogu上的这道题，但是这个一直段错误，难受，不知道原因。
#include<bits/stdc++.h> #define il inline #define pb push_back #define fi first #define se second #define ms(_data,v) memset(_data,v,sizeof(_data)) #define sc(n) scanf("%d",&n) #define SC(n,m) scanf("%d %d",&n,&m) #define SZ(a) int((a).size()) #define rep(i,a,b) for(int i=a;i<=b;++i) #define drep(i,a,b) for(int i=a;i>=b;--i) using namespace std; typedef long long ll; const ll inf=0x3f3f3f3f; const double PI=acos(-1.0); const double eps=1e-9; const int maxn=1e5+5; unordered_map<int,int> rk; int T,n,m,tot,sz,a[maxn],b[maxn*5]; struct tree{ int l,r,x; }t[maxn*900]; int root[maxn],root1[maxn],cnt,tot1,tot2,q1[maxn],q2[maxn]; il int update(int l,int r,int last,int k,int op){ int rt=++cnt; t[rt]=t[last],t[rt].x+=op; if(l==r) return rt; int mid=(l+r)>>1; if(k<=mid) t[rt].l=update(l,mid,t[last].l,k,op); else t[rt].r=update(mid+1,r,t[last].r,k,op); return rt; } il int query(int l,int r,int s1,int s2,int k){ if(l==r) return l; int x=t[t[s2].l].x-t[t[s1].l].x; rep(i,1,tot1) x-=t[t[q1[i]].l].x; rep(i,1,tot2) x+=t[t[q2[i]].l].x; int mid=(l+r)>>1; if(x>=k){ rep(i,1,tot1) q1[i]=t[q1[i]].l; rep(i,1,tot2) q2[i]=t[q2[i]].l; return query(l,mid,t[s1].l,t[s2].l,k); } else{ rep(i,1,tot1) q1[i]=t[q1[i]].r; rep(i,1,tot2) q2[i]=t[q2[i]].r; return query(mid+1,r,t[s1].r,t[s2].r,k-x); } } struct node{ int op,l,r,k; }q[maxn]; il void runrk(){ sort(b+1,b+tot+1); sz=unique(b+1,b+tot+1)-(b+1); rep(i,1,sz) rk[b[i]]=i; } int main(){ sc(T); while(T--){ SC(n,m); tot=0,cnt=0,rk.clear(); rep(i,1,n) sc(a[i]),b[++tot]=a[i]; char op; int l,r,k; rep(i,1,m){ op=getchar(); while(!(op=='Q' || op=='C')) op=getchar(); if(op=='Q'){ SC(l,r),sc(k); q[i]=node{1,l,r,k}; } else{ SC(l,r); b[++tot]=r; q[i]=node{0,l,r,0}; } } runrk(); root[0]=root[1]=0; rep(i,1,n) root1[i]=root[1]; rep(i,1,n) root[i]=update(1,sz,root[i-1],rk[a[i]],1); rep(i,1,m){ if(q[i].op){ //query int x=q[i].l-1,y=q[i].r,k=q[i].k; tot1=0,tot2=0; while(x){ q1[++tot1]=root1[x]; x-=x&-x; } while(y){ q2[++tot2]=root1[y]; y-=y&-y; } int id=query(1,sz,root[q[i].l-1],root[q[i].r],k); printf("%d\n",b[id]); } else{ // modify int x=q[i].l,now=rk[q[i].r],pre=rk[a[x]]; a[x]=q[i].r; while(x<=n){ root1[x]=update(1,sz,root1[x],pre,-1); root1[x]=update(1,sz,root1[x],now,1); x+=x&-x; } } } } return 0; }
