首页 > 代码库 > 【复习笔记】主席树
【复习笔记】主席树
昨天在写带修改主席树的时候，咸鱼zcysky发现自己似乎根本不会写主席树
于是正好找个空复习下……
主席树的原理不用我扯了，主席树为啥能求k大，大概在它可以用历史版本存下区间的前缀和，求的时候差分下就能提出我要求的区间。
不过这么搞的话不要忘了离散化。
1.kth number
就是上面的裸题，不要手贱写bits就好。
1 #include<iostream> 2 #include<cstdio> 3 #define N 100010 4 #include<algorithm> 5 #include<cstring> 6 using namespace std; 7 struct Node{int sum,ls,rs;}T[N*20]; 8 int cnt; 9 void ins(int &num,int &x,int l,int r){ 10 T[cnt++]=T[x];x=cnt-1;T[x].sum++; 11 if(l==r)return; 12 int mid=(l+r)/2; 13 if(num<=mid)ins(num,T[x].ls,l,mid); 14 else ins(num,T[x].rs,mid+1,r); 15 } 16 int query(int i,int j,int k,int l,int r){ 17 if(l==r)return l; 18 int t=T[T[j].ls].sum-T[T[i].ls].sum; 19 int mid=(l+r)/2; 20 if(k<=t)return query(T[i].ls,T[j].ls,k,l,mid); 21 else return query(T[i].rs,T[j].rs,k-t,mid+1,r); 22 } 23 struct A{ 24 int x,idx; 25 bool operator<(const A &s)const{ 26 return x<s.x;} 27 }; 28 A a[N]; 29 int rank[N],root[N]; 30 int n,m; 31 int main(){ 32 T[0].ls=T[0].rs=T[0].sum=0;root[0]=0; 33 while(scanf("%d%d",&n,&m)!=EOF){ 34 for(register int i=1;i<=n;++i){ 35 scanf("%d",&a[i].x); 36 a[i].idx=i; 37 } 38 sort(a+1,a+n+1); 39 for(int i=1;i<=n;i++)rank[a[i].idx]=i; 40 cnt=1; 41 for(int i=1;i<=n;i++){ 42 root[i]=root[i-1]; 43 ins(rank[i],root[i],1,n); 44 } 45 while(m--){ 46 int i,j,k; 47 scanf("%d%d%d",&i,&j,&k); 48 int ans=a[query(root[i-1],root[j],k,1,n)].x; 49 printf("%d\n",ans); 50 } 51 } 52 return 0; 53 }
哦注明下，这是我高一上学期写的，码风清奇……
不过总有人喜欢的。
2.luoogu P3567,bzoj3524 couriers（权限题）
真是的要什么权限题！洛谷提交地址
随手记录下size就好啦，不过这题甚至不用离散化23333
1 #include<bits/stdc++.h> 2 #define N 500005 3 using namespace std; 4 int n,m,a[N],ls[25*N],rs[25*N],size[25*N],cnt=0,rt[N]; 5 void ins(int &o,int pre,int l,int r,int q){ 6 o=++cnt;int mid=(l+r)>>1; 7 ls[o]=ls[pre];rs[o]=rs[pre];size[o]=size[pre]+1; 8 if(l==r)return; 9 if(q<=mid)ins(ls[o],ls[pre],l,mid,q); 10 else ins(rs[o],rs[pre],mid+1,r,q); 11 } 12 int query(int x,int y,int l,int r,int q){ 13 if(l==r)return l;int mid=(l+r)>>1; 14 int lsize=(size[ls[x]]-size[ls[y]]),rsize=(size[rs[x]]-size[rs[y]]); 15 if(lsize>q)return query(ls[x],ls[y],l,mid,q); 16 else if(rsize>q)return query(rs[x],rs[y],mid+1,r,q); 17 else return 0; 18 } 19 inline int read(){ 20 int f=1,x=0;char ch; 21 do{ch=getchar();if(ch==‘-‘)f=-1;}while(ch<‘0‘||ch>‘9‘); 22 do{x=x*10+ch-‘0‘;ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘); 23 return f*x; 24 } 25 int main(){ 26 n=read();m=read(); 27 for(int i=1;i<=n;i++)a[i]=read(); 28 for(int i=1;i<=n;i++)ins(rt[i],rt[i-1],1,n,a[i]); 29 while(m--){ 30 int l=read(),r=read(); 31 printf("%d\n",query(rt[r],rt[l-1],1,n,(r-l+1)>>1)); 32 } 33 return 0; 34 }
3.mex
啥是mex？就是SG函数的mex啊。
之前写的莫队，后来发现主席树也很资瓷。
注意从0开始就好。
1 #include<bits/stdc++.h> 2 #define N 300005 3 #define M 6000005 4 using namespace std; 5 int n,q,cnt,a[N],ls[M],rs[M],rt[M],minv[M]; 6 void ins(int &x,int fa,int l,int r,int q,int val){ 7 x=++cnt;minv[x]=minv[fa]; 8 ls[x]=ls[fa];rs[x]=rs[fa]; 9 if(l==r){minv[x]=val;return;} 10 int mid=(l+r)>>1; 11 if(q<=mid)ins(ls[x],ls[fa],l,mid,q,val); 12 else ins(rs[x],rs[fa],mid+1,r,q,val); 13 minv[x]=min(minv[ls[x]],minv[rs[x]]); 14 } 15 int query(int x,int l,int r,int q){ 16 if(l==r)return l; 17 int mid=(l+r)>>1; 18 if(minv[ls[x]]>=q)return query(rs[x],mid+1,r,q); 19 else return query(ls[x],l,mid,q); 20 } 21 inline int read(){ 22 int f=1,x=0;char ch; 23 do{ch=getchar();if(ch==‘-‘)f=-1;}while(ch<‘0‘||ch>‘9‘); 24 do{x=x*10+ch-‘0‘;ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘); 25 return f*x; 26 } 27 int main(){ 28 n=read();q=read(); 29 for(int i=1;i<=n;i++)a[i]=read(); 30 for(int i=1;i<=n;i++)ins(rt[i],rt[i-1],0,1000000,a[i],i); 31 while(q--){ 32 int x=read(),y=read(); 33 printf("%d\n",query(rt[y],0,1000000,x)); 34 } 35 return 0; 36 }
4.dynamic ranking
详见之前blog。
1 #include<bits/stdc++.h> 2 #define N 10005 3 using namespace std; 4 inline int lowbit(int x){return x&-x;} 5 int n,m,sz,totn,totx,toty,a[N],b[N<<1],ca[N],cb[N],cc[N]; 6 int xx[N],yy[N],rt[N],size[600*N],ls[600*N],rs[600*N]; 7 void ins(int &o,int l,int r,int x,int q,int v){ 8 o=++sz;size[o]=size[x]+v;ls[o]=ls[x];rs[o]=rs[x]; 9 if(l==r)return;int mid=(l+r)>>1; 10 if(q<=mid)ins(ls[o],l,mid,ls[x],q,v); 11 else ins(rs[o],mid+1,r,rs[x],q,v); 12 } 13 int query(int l,int r,int q){ 14 if(l==r)return l; 15 int sum=0,mid=(l+r)>>1; 16 for(int i=1;i<=totx;i++)sum-=size[ls[xx[i]]]; 17 for(int i=1;i<=toty;i++)sum+=size[ls[yy[i]]]; 18 if(q<=sum){ 19 for(int i=1;i<=totx;i++)xx[i]=ls[xx[i]]; 20 for(int i=1;i<=toty;i++)yy[i]=ls[yy[i]]; 21 return query(l,mid,q); 22 } 23 else{ 24 for(int i=1;i<=totx;i++)xx[i]=rs[xx[i]]; 25 for(int i=1;i<=toty;i++)yy[i]=rs[yy[i]]; 26 return query(mid+1,r,q-sum); 27 } 28 } 29 void add(int x,int v){ 30 int k=lower_bound(b+1,b+totn+1,a[x])-b; 31 for(int i=x;i<=n;i+=lowbit(i))ins(rt[i],1,totn,rt[i],k,v); 32 } 33 inline int read(){ 34 int f=1,x=0;char ch; 35 do{ch=getchar();if(ch==‘-‘)f=-1;}while(ch<‘0‘||ch>‘9‘); 36 do{x=x*10+ch-‘0‘;ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘); 37 return f*x; 38 } 39 int main(){char s[20]; 40 n=read();m=read(); 41 for(int i=1;i<=n;i++)a[i]=read(),b[++totn]=a[i]; 42 for(int i=1;i<=m;i++){ 43 scanf("%s",s);ca[i]=read();cb[i]=read(); 44 if(s[0]==‘Q‘)cc[i]=read();else b[++totn]=cb[i]; 45 } 46 sort(b+1,b+totn+1); 47 totn=unique(b+1,b+totn+1)-b-1; 48 for(int i=1;i<=n;i++)add(i,1); 49 for(int i=1;i<=m;i++){ 50 if(cc[i]){ 51 totx=toty=0; 52 for(int j=ca[i]-1;j;j-=lowbit(j))xx[++totx]=rt[j]; 53 for(int j=cb[i];j;j-=lowbit(j))yy[++toty]=rt[j]; 54 printf("%d\n",b[query(1,totn,cc[i])]); 55 } 56 else{add(ca[i],-1);a[ca[i]]=cb[i];add(ca[i],1);} 57 } 58 }
5.任务查询系统
这里是bzoj的地址：http://www.lydsy.com/JudgeOnline/problem.php?id=3932
按照时间随意差分，差分完上树就行。
1 #include<bits/stdc++.h> 2 #define N 100005 3 using namespace std; 4 int n,m,pre=1,totn,h[N],rt[N],cnt=0,ls[50*N],rs[50*N],size[50*N],sumv[50*N]; 5 vector<int>a[N]; 6 void ins(int &o,int pre,int l,int r,int q,int v){ 7 o=++cnt;ls[o]=ls[pre];rs[o]=rs[pre]; 8 size[o]=size[pre]+v;sumv[o]=sumv[pre]+h[q]*v; 9 if(l==r)return;int mid=(l+r)>>1; 10 if(q<=mid)ins(ls[o],ls[pre],l,mid,q,v); 11 else ins(rs[o],rs[pre],mid+1,r,q,v); 12 } 13 int query(int o,int l,int r,int q){ 14 if(q>=size[o])return sumv[o]; 15 if(l==r)return sumv[o]/size[o]*q; 16 int mid=(l+r)>>1,ans=query(ls[o],l,mid,q); 17 if(q>size[ls[o]])ans+=query(rs[o],mid+1,r,q-size[ls[o]]); 18 return ans; 19 } 20 inline int read(){ 21 int f=1,x=0;char ch; 22 do{ch=getchar();if(ch==‘-‘)f=-1;}while(ch<‘0‘||ch>‘9‘); 23 do{x=x*10+ch-‘0‘;ch=getchar();}while(ch>=‘0‘&&ch<=‘9‘); 24 return f*x; 25 } 26 int main(){ 27 m=read();n=read(); 28 for(int i=1;i<=m;i++){ 29 int x=read(),y=read(),z=read(); 30 a[x].push_back(z);a[y+1].push_back(-z); 31 h[i]=z; 32 } 33 sort(h+1,h+m+1);totn=unique(h+1,h+m+1)-h-1; 34 for(int i=1;i<=n;i++){ 35 rt[i]=rt[i-1]; 36 for(int j=0;j<a[i].size();j++){ 37 int k=1;if(a[i][j]<0)k*=-1,a[i][j]*=-1; 38 ins(rt[i],rt[i],1,totn,lower_bound(h+1,h+totn+1,a[i][j])-h,k); 39 } 40 } 41 while(n--){ 42 int X=read(),A=read(),B=read(),C=read(); 43 printf("%d\n",pre=query(rt[X],1,totn,1+((long long)A*pre+B)%C)); 44 } 45 return 0; 46 }
啊呸这鬼题目，n,m怎么是反的啊！
为了这个sb错误找半天的zcysky是不是也是sb啊……
【复习笔记】主席树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。