学习粗：https://blog.csdn.net/creatorx/article/details/75446472
主要解决 可查询历史版本的线段树，区间第k大问题
我们询问【L,R】时，我们就认为是第R棵树减去第L-1棵树；（详情：https://blog.csdn.net/bestFy/article/details/78650360）
在询问时我们以root[]进行区间查询，因为我们我们在建的时候（update）已经按照分树来做，所以第一步传入的位置正确的话，又因为结构体内已存入左右孩子，所以顺传下去。就是对的，
题1：http://poj.org/problem?id=2104（静态主席树）
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; inline int read(){ int sum=0,x=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') x=0; ch=getchar(); } while(ch>='0'&&ch<='9') sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar(); return x?sum:-sum; } inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } const int M=1e5+5; struct node{ int sum,L,R; }tree[M*40]; int root[M],a[M],b[M],n,m,cnt; void build(int &now,int l,int r){ now=++cnt; if(l==r) return ; int midd=(l+r)>>1; build(tree[now].L,l,midd); build(tree[now].R,midd+1,r); } void update(int &rt,int pos,int l,int r){ tree[++cnt]=tree[rt]; tree[cnt].sum++; rt=cnt; if(l==r) return ; int midd=(l+r)>>1; if(pos<=midd) update(tree[rt].L,pos,l,midd); else update(tree[rt].R,pos,midd+1,r); } int query(int i,int j,int k,int l,int r){ int num=tree[tree[j].L].sum-tree[tree[i].L].sum; if(l==r) return l; int midd=(l+r)>>1; if(num>=k) return query(tree[i].L,tree[j].L,k,l,midd); else return query(tree[i].R,tree[j].R,k-num,midd+1,r); } int main(){ n=read(),m=read(); for(int i=1;i<=n;i++) a[i]=read(),b[i]=a[i]; sort(b+1,b+1+n); int p=unique(b+1,b+1+n)-b-1; // build(root[0],1,p); for(int i=1;i<=n;i++){ root[i]=root[i-1]; int pos=lower_bound(b+1,b+1+p,a[i])-b; update(root[i],pos,1,p); } while(m--){ int l,r,k; l=read(),r=read(),k=read(); write(b[query(root[l-1],root[r],k,1,p)]); putchar(' '); } return 0; }
题2：https://www.luogu.org/problem/P3567
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; inline int read(){ int sum=0,x=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') x=0; ch=getchar(); } while(ch>='0'&&ch<='9') sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar(); return x?sum:-sum; } inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } const int M=1e5+5; struct node{ int sum,L,R; }tree[M*40]; int root[M],a[M],b[M],n,m,cnt; void build(int &now,int l,int r){ now=++cnt; if(l==r) return ; int midd=(l+r)>>1; build(tree[now].L,l,midd); build(tree[now].R,midd+1,r); } void update(int &rt,int pos,int l,int r){ tree[++cnt]=tree[rt]; tree[cnt].sum++; rt=cnt; if(l==r) return ; int midd=(l+r)>>1; if(pos<=midd) update(tree[rt].L,pos,l,midd); else update(tree[rt].R,pos,midd+1,r); } int query(int i,int j,int len,int l,int r){ if(l==r) return l; int lsum=tree[tree[j].L].sum-tree[tree[i].L].sum; int rsum=tree[tree[j].R].sum-tree[tree[i].R].sum; int midd=(l+r)>>1; if(lsum>len) return query(tree[i].L,tree[j].L,len,l,midd); else if(rsum>len) return query(tree[i].R,tree[j].R,len,midd+1,r); return 0; } int main(){ n=read(),m=read(); for(int i=1;i<=n;i++) a[i]=read(),b[i]=a[i]; sort(b+1,b+1+n); int p=unique(b+1,b+1+n)-b-1; // build(root[0],1,p); for(int i=1;i<=n;i++){ root[i]=root[i-1]; int pos=lower_bound(b+1,b+1+p,a[i])-b; update(root[i],pos,1,p); } while(m--){ int l,r; l=read(),r=read(); int len=(r-l+1)>>1; write(b[query(root[l-1],root[r],len,1,p)]); putchar(' '); } return 0; }
可持续化数组（主席树实现）
题：https://www.luogu.org/problem/P3919
可持久化数组可以用可持久化线段树实现
然后实现的方法就是每次在对应的历史版本进行path-copy。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define pb push_back inline int read(){ int sum=0,x=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') x=0; ch=getchar(); } while(ch>='0'&&ch<='9') sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar(); return x?sum:-sum; } inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } const int M=1e6+6; struct node{ int val,L,R; }tree[M*20]; int root[M],a[M],cnt; void build(int &now,int l,int r){ now=++cnt; if(l==r){ tree[now].val=a[l]; return ; } int midd=(l+r)>>1; build(tree[now].L,l,midd); build(tree[now].R,midd+1,r); } void update(int &rt,int pre,int x,int val,int l,int r){ rt=++cnt; tree[rt]=tree[pre]; if(l==r){ tree[rt].val=val; return ; } int midd=(l+r)>>1; if(x<=midd) update(tree[rt].L,tree[pre].L,x,val,l,midd); else update(tree[rt].R,tree[pre].R,x,val,midd+1,r); } int query(int rt,int x,int l,int r){ if(l==r) return tree[rt].val; int midd=(l+r)>>1; if(x<=midd) return query(tree[rt].L,x,l,midd); else return query(tree[rt].R,x,midd+1,r); } int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(root[0],1,n); // cout<<cnt<<endl; for(int i=1;i<=m;i++){ int banben,op,x; scanf("%d%d%d",&banben,&op,&x); if(op==1){ int y; scanf("%d",&y); update(root[i],root[banben],x,y,1,n);///先对之前版本进行copy，再进行修改操作，便实现了题目的要求 } else{ printf("%d ",query(root[banben],x,1,n)); root[i]=root[banben]; } } return 0; }
主席树+（二维前缀+二分）二合一题：https://www.luogu.org/problem/P2468
#include<bits/stdc++.h> using namespace std; int n,m,q; int sum[210][210][1003],num[210][210][1003]; int a[210][210]; int getsum(int x1,int y1,int x2,int y2,int k){ return sum[x2][y2][k]-sum[x2][y1-1][k]-sum[x1-1][y2][k]+sum[x1-1][y1-1][k]; } int getnum(int x1,int y1,int x2,int y2,int k){ return num[x2][y2][k]-num[x2][y1-1][k]-num[x1-1][y2][k]+num[x1-1][y1-1][k]; } void solve2(){ //预处理 int maxx=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]),maxx=max(maxx,a[i][j]); //cout<<maxx<<endl; for(int k=0;k<=maxx;k++) for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ if(a[i][j]>=k){ sum[i][j][k]=sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k]+a[i][j]; num[i][j][k]=num[i-1][j][k]+num[i][j-1][k]-num[i-1][j-1][k]+1; } else{ sum[i][j][k]=sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k]; num[i][j][k]=num[i-1][j][k]+num[i][j-1][k]-num[i-1][j-1][k]; } } /*for(int i=1;i<=n;i++){ / for(int j=1;j<=m;j++) cout<<sum[i][j][15]<<" "; cout<<endl; }*/ while(q--){ int x1,y1,x2,y2,h; scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&h); if(getsum(x1,y1,x2,y2,0)<h){ printf("Poor QLW "); continue; } int l=0,r=maxx,ans; while(l<=r){ int midd=(l+r)>>1; if(getsum(x1,y1,x2,y2,midd)>=h) l=midd+1,ans=midd; else r=midd-1; } //我们二分的k值，有可能=k的数有很多，会多出来很多无用的k。无用的k的和就是sum(a,b,c,d,k)-h，用无用的和除以k即得到多出来的k的数量，减去就好了。 printf("%d ",getnum(x1,y1,x2,y2,ans)-(getsum(x1,y1,x2,y2,ans)-h)/ans);//若有多余的就减去多余的 } } const int M=5e5+5; int root[M]; struct node{ int L,R,sum,w; }tree[M<<5]; int cnt; void update(int &now,int pos,int l,int r){ tree[++cnt]=tree[now]; tree[cnt].sum+=pos; tree[cnt].w++; now=cnt; if(l==r) return ; int midd=(l+r)>>1; if(pos<=midd) update(tree[now].L,pos,l,midd); else update(tree[now].R,pos,midd+1,r); } int query(int i,int j,int l,int r,int k) { if(l==r) return (k+l-1)/l;///到叶子节点，意味着此区间只含有数值为l的节点，多少个不清楚，所以向上取整个数 int midd=(l+r)>>1; int w=tree[tree[j].R].sum-tree[tree[i].R].sum; if(k<=w) return query(tree[i].R,tree[j].R,midd+1,r,k); else return query(tree[i].L,tree[j].L,l,midd,k-w)+tree[tree[j].R].w-tree[tree[i].R].w; } void solve1(){ for(int i=1;i<=m;i++){ int x; scanf("%d",&x); root[i]=root[i-1]; update(root[i],x,1,1000); } while(q--){ int x1,y1,x2,y2,h; scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&h); if(tree[root[y2]].sum-tree[root[y1-1]].sum<h){ printf("Poor QLW "); } else printf("%d ",query(root[y1-1],root[y2],1,1000,h)); } } int main(){ scanf("%d%d%d",&n,&m,&q); if(n==1) solve1(); else solve2(); return 0; }