可持久化数据结构板子整理(可持久化 线段树/字典树/可并堆)
主席树静态序列查区间第k大
struct tree{ int L,R,sum; }t[100010]; void change(int &now,int pre,int l,int r,int k){ now=++cnt; t[now]=t[pre]; t[now].sum++; int mid=(l+r)/2; if(l<r){ if(k<=mid){ change(t[now].L,t[pre].L,l,mid,k); }else{ change(t[now].R,t[pre].R,mid+1,r,k); } } } int query(int xl,int xr,int l,int r,int k){ if(l==r)return l; int x=t[t[xr].L].sum-t[t[xl].L].sum; int mid=(l+r)/2; if(x>=k){ return query(t[xl].L,t[xr].L,l,mid,k); }else{ return query(t[xl].R,t[xr].R,mid+1,r,k-x); } }
主席树可持久化数组
struct tree{ int L,R,w; }t[100010]; void change(int &now,int pre,int x,int y,int l,int r){ now=++cnt; if(l==r){ t[now].w=y; return; } t[now].L=t[pre].L; t[now].R=t[pre].R; int mid=(l+r)/2; if(x<=mid){ change(t[now].L,t[pre].L,x,y,l,mid); }else{ change(t[now].R,t[pre].R,x,y,mid+1,r); } return ; } int query(int pre,int x,int l,int r){ if(l==r){ return t[pre].w; } int mid=(l+r)/2; if(x<=mid){ return query(t[pre].L,x,l,mid); }else{ return query(t[pre].R,x,mid+1,r); } }
可持久化字典树
struct trie{ int ch[2],siz,id; }t[50000010]; void change(int &now,int pre,int bit,long long val){ now=++cnt; t[now]=t[pre]; t[now].siz++; if(bit==-1){ return; } int i=(val>>bit)&1; change(t[now].ch[i],t[pre].ch[i],bit-1,val); } int query(int a,int b,int bit,long long val){ if(bit<0){ return 0; } int i=(val>>bit)&1; if(t[t[b].ch[!i]].siz-t[t[a].ch[!i]].siz>0){ return (1<<bit)+query(t[a].ch[!i],t[b].ch[!i],bit-1,val); }else{ return query(t[a].ch[i],t[b].ch[i],bit-1,val); } }
可持久化可并堆
struct Heap{ int ls,rs,dist; int w; }t[3000010]; int merge(int x,int y){ if(!x||!y)return x+y; if(t[x].w>=t[y].w)swap(x,y); int p=++cnt; t[p]=t[x]; t[p].rs=merge(t[p].rs,y); if(t[t[p].ls].dist<t[t[p].rs].dist)swap(t[p].ls,t[p].rs); t[p].dist=t[t[x].rs].dist+1; return p; } int newheap(int w,int to){ int x=++cnt; t[x].w=w; t[x].dist=1; return x; }