主席树

主席树 P3919 【模板】可持久化线段树 1（可持久化数组） #include using namespace std; #define lc tr[p].l #define rc tr[p].r const int N=1e6+5; int n,m,idx; int a[N],rot[N]; struct tree{ int x,l,r; }tr[N*24]; int build(int l,int r){ int p=++idx; if(l==r){ tr[p].x=a[l]; return p; } int mid=l+r>>1; lc=build(l,mid); rc=build(mid+1,r); return p; } int change(int p,int l,int r,int x,int y){ tr[++idx]=tr[p],p=idx; if(l==r){ tr[p].x=y; return p; } int mid=l+r>>1; if(x>1; if(x>n>>m; for(int i=1;i>a[i]; rot[0]=build(1,n); for(int i=1;i>v>>op>>x; if(op==1){ cin>>y; rot[i]=change(rot[v],1,n,x,y); } else{ cout `#include using namespace std; #define lc tr[p].l #define rc tr[p].r const int N=1e6+5; int n,m,idx; int a[N],rot[N]; struct tree{ int x,l,r; }tr[N*24]; int build(int l,int r){ int p=++idx; if(l==r){ tr[p].x=a[l]; return p; } int mid=l+r>>1; lc=build(l,mid); rc=build(mid+1,r); return p; } int change(int p,int l,int r,int x,int y){ tr[++idx]=tr[p],p=idx; if(l==r){ tr[p].x=y; return p; } int mid=l+r>>1; if(xchange(lc,l,mid,x,y); else rc=change(rc,mid+1,r,x,y); return p; } int check(int p,int l,int r,int x){ if(l==r) return tr[p].x; int mid=l+r>>1; if(xreturn check(lc,l,mid,x); else return check(rc,mid+1,r,x); } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=1;i>a[i]; rot[0]=build(1,n); for(int i=1;i int v,op,x,y; cin>>v>>op>>x; if(op==1){ cin>>y; rot[i]=change(rot[v],1,n,x,y); } else{ coutcheck(rot[v],1,n,x)"\n"; rot[i]=rot[v]; } } return 0; }` P3834 【模板】可持久化线段树 2 #include using namespace std; #define N 200005 #define lc(x) tr[x].l #define rc(x) tr[x].r struct node{ int l,r,s; }tr[N*20]; int root[N],idx; int n,m,a[N],b[N]; void insert(int x,int &y,int l,int r,int pos){ y=++idx; tr[y]=tr[x]; tr[y].s++; if(l==r) return; int m=l+r>>1; if(pos>1; int s=tr[lc(y)].s-tr[lc(x)].s; if(k `#include using namespace std; #define N 200005 #define lc(x) tr[x].l #define rc(x) tr[x].r struct node{ int l,r,s; }tr[N*20]; int root[N],idx; int n,m,a[N],b[N]; void insert(int x,int &y,int l,int r,int pos){ y=++idx; tr[y]=tr[x]; tr[y].s++; if(l==r) return; int m=l+r>>1; if(posinsert(lc(x),lc(y),l,m,pos); else insert(rc(x),rc(y),m+1,r,pos); } int query(int x,int y,int l,int r,int k){ if(l==r) return l; int m=l+r>>1; int s=tr[lc(y)].s-tr[lc(x)].s; if(kreturn query(lc(x),lc(y),l,m,k); else return query(rc(x),rc(y),m+1,r,k-s); } int main(){ scanf("%d%d",&n,&m); for(int i=1; i scanf("%d",&a[i]); b[i]=a[i]; } sort(b+1,b+n+1); int bn=unique(b+1,b+n+1)-b-1; for(int i=1;i int id=lower_bound(b+1,b+bn+1,a[i])-b; insert(root[i-1],root[i],1,bn,id); } while(m--){ int l,r,k; scanf("%d%d%d",&l,&r,&k); int id=query(root[l-1],root[r],1,bn,k); printf("%d\n",b[id]); } return 0; }`