\[ \ \]
(那些说这道题是树状数组套主席树的人一定对主席树有误解!)
这里我们用树状数组套线段树来解决来写
首先 , 我们需要有n棵线段树(不是\(n^2\)空间,别慌)
我们用这些线段树存储值域$ [l,r] $内数的个数
基于主席树的思想,我们的线段树是要相减的,记录的是前缀
由于要更新前缀,我们必须快速更新,所以采用树状数组来写
事实上,这里线段树的本质并非主席树,而是动态开点的线段树
(这两者是有显著差异的)
这是主席数的单点修改
struct Functional_SegmentTree{ void Add(int p,int pre,int l,int r,int x,int y){ s[p]=s[pre]+y; if(l==r) return; int mid=(l+r)>>1; if(x<=mid) rs[p]=rs[pre],Add(ls[p]=++cnt,ls[pre],l,mid,x,y); else ls[p]=ls[pre],Add(rs[p]=++cnt,rs[pre],mid+1,r,x,y); } };是路径上的所有点都要新开节点,而实际上动点线段树不是开新点,只是当你的儿子要访问了却还未开出来时才需要开
所以代码应该是这样的
void Add(int p,int l,int r,int x,int y){ s[p]+=y; if(l==r) return; int mid=(l+r)>>1; if(x<=mid) Add(ls[p]?ls[p]:(ls[cnt+1]=rs[cnt+1]=s[cnt+1]=0,ls[p]=++cnt),l,mid,x,y); else Add(rs[p]?rs[p]:(ls[cnt+1]=rs[cnt+1]=s[cnt+1]=0,rs[p]=++cnt),mid+1,r,x,y); }(略有压行)
所以整体上应该是树状数组更新动点线段树
但是由于这题卡空间 (过于罪恶)
所以我们应该先开一个主席树存下原来的值
(为什么这样能省空间呢?因为树状数组更新的空间复杂度是\(log^2(n)\)，主席树更新是log(n)的)
于是代码会长这样
const int N=50100,M=10010,K=1520110; int n,m; int ncnt; int a[N],b[N+M],c[M],d[M],e[M]; int cnt; int ls[K],rs[K],s[K]; int rt[N]; struct hjt{ void Add(int p,int pre,int l,int r,int x,int y){ s[p]=s[pre]+y; if(l==r) return; int mid=(l+r)>>1; if(x<=mid) rs[p]=rs[pre],Add(ls[p]=++cnt,ls[pre],l,mid,x,y); else ls[p]=ls[pre],Add(rs[p]=++cnt,rs[pre],mid+1,r,x,y); } }H; struct sts{ void Add(int p,int l,int r,int x,int y){ s[p]+=y; if(l==r) return; int mid=(l+r)>>1; if(x<=mid) Add(ls[p]?ls[p]:(ls[cnt+1]=rs[cnt+1]=s[cnt+1]=0,ls[p]=++cnt),l,mid,x,y); else Add(rs[p]?rs[p]:(ls[cnt+1]=rs[cnt+1]=s[cnt+1]=0,rs[p]=++cnt),mid+1,r,x,y); } int T[N]; vector <int> X,Y; int Que(int l,int r,int k){ if(l==r) return l; int mid=(l+r)>>1; int t=0; rep(i,0,X.size()-1) t+=s[ls[X[i]]]; rep(i,0,Y.size()-1) t-=s[ls[Y[i]]]; if(t>=k) { rep(i,0,X.size()-1) X[i]=ls[X[i]]; rep(i,0,Y.size()-1) Y[i]=ls[Y[i]]; return Que(l,mid,k); } else { rep(i,0,X.size()-1) X[i]=rs[X[i]]; rep(i,0,Y.size()-1) Y[i]=rs[Y[i]]; return Que(mid+1,r,k-t); } } int query(int l,int r,int k){ int p=r; X.clear();X.push_back(rt[r]); while(p) X.push_back(T[p]),p-=p&-p; p=l-1;Y.clear();Y.push_back(rt[l-1]); while(p) Y.push_back(T[p]),p-=p&-p; return Que(1,ncnt,k); } void Upd(int p,int x,int y){ while(p<=n) Add(T[p]?T[p]:(ls[cnt+1]=rs[cnt+1]=s[cnt+1]=0,T[p]=++cnt),1,ncnt,x,y),p+=p&-p; } }S; char opt[N][1]; int main(){ rep(kase,1,rd()){ n=rd(),m=rd(); cnt=0; memset(S.T,0,sizeof S.T); rep(i,1,n) a[i]=b[i]=rd(); ncnt=n; rep(i,1,m) { scanf("%s",opt[i]); if(opt[i][0]=='Q'){ c[i]=rd(),d[i]=rd(),e[i]=rd(); } else { c[i]=rd(),d[i]=rd(); b[++ncnt]=d[i]; } } sort(b+1,b+ncnt+1);ncnt=unique(b+1,b+ncnt+1)-b-1; rep(i,1,n) { a[i]=lower_bound(b+1,b+ncnt+1,a[i])-b; H.Add(rt[i]=++cnt,rt[i-1],1,ncnt,a[i],1); } rep(i,1,m){ if(opt[i][0]=='Q'){ int ans=S.query(c[i],d[i],e[i]); printf("%d\n",b[ans]); }else { d[i]=lower_bound(b+1,b+ncnt+1,d[i])-b; S.Upd(c[i],a[c[i]],-1); S.Upd(c[i],a[c[i]]=d[i],1); } } } }转载于:https://www.cnblogs.com/chasedeath/p/11259367.html
相关资源：JAVA上百实例源码以及开源项目