ZR 集训 Day4 – 平衡树及其应用 · ooliver

ZR 集训 Day4 – 平衡树及其应用 P6136 【模板】普通平衡树（数据加强版）（P3369 【模板】普通平衡树）这俩就改改输入的区别，就按加强版来讲了。这里使用的是 FHQ Treap，因为它非常简洁易懂，只需要核心掌握两个操作：分裂和合并。分裂分裂函数需要四个参数 u,key,x,y，意思是将以 u 为根的 Treap 按 key 分裂成以 x，y 为根的两个子树。 **具体实现：**若当前子树的根 u 的权值小于或等于 key，那就把 x 设为 u，把 u 的左儿子分给 x，并递归 u 的右儿子，将右儿子中小于或等于 key 的分到 x 的右儿子，其余分给 y；反之亦然。 C++ void pushup(int u){ sz[u]=sz[ch[u][0]]+sz[ch[u][1]]+1; } void split(int u,int key,int &x,int &y){ if(!u){ x=y=0; return; } if(val[u] `void pushup(int u){ sz[u]=sz[ch[u][0]]+sz[ch[u][1]]+1; } void split(int u,int key,int &x,int &y){ if(!u){ x=y=0; return; } if(val[u]key) x=u,split(ch[u][1],key,ch[u][1],y); else y=u,split(ch[u][0],key,x,ch[u][0]); pushup(u); }` 合并合并 x，y 两颗 Treap 的前提是 x 内的全部权值都要小于 y 内的任意一个权值。比较两颗 Treap 的随机优先级，将优先级低的合并到优先级高的上。若 x 优先级更高，则将 y 与 x 的右儿子递归合并；反之亦然。 C++ int merge(int x,int y){ if(!x||!y) return x+y; if(rnd[x] `int merge(int x,int y){ if(!x||!y) return x+y; if(rnd[x]rnd[y]){ ch[x][1]=merge(ch[x][1],y); pushup(x); return x; } else{ ch[y][0]=merge(x,ch[y][0]); pushup(y); return y; } }` 添加添加一个权值为 v 的点。先根据权值 v 建一个点 u。定义两颗子树，将原 Treap 按照 v 分裂成两部分，再加上新建节点 u 一起合并即可。 C++ int newd(int v){ val[++idx]=v,sz[idx]=1,rnd[idx]=rand(); ch[idx][0]=ch[idx][1]=0; return idx; } void insert(int v){ int x,y,u=newd(v); split(rt,v,x,y); rt=merge(merge(x,u),y); } `int newd(int v){ val[++idx]=v,sz[idx]=1,rnd[idx]=rand(); ch[idx][0]=ch[idx][1]=0; return idx; } void insert(int v){ int x,y,u=newd(v); split(rt,v,x,y); rt=merge(merge(x,u),y); }` 删除删除一个权值为 v 的点。先按照 v-1 把原 Treap 分裂成两个子树 x 和 y，再按照 v 把 y 分裂成 y 和 z。此时 x 内点权全部小于 v，y 内点权全部等于 v，z 内点权全部大于 v。此时直接合并 y 的左右儿子，相当于不管 y 这个根了，最后再把 x，y，z 合并起来，就完成了。 C++ void del(int v){ int x,y,z; split(rt,v-1,x,y); split(y,v,y,z); if(!y){ rt=merge(x,z); return; } y=merge(ch[y][0],ch[y][1]); rt=merge(x,merge(y,z)); } `void del(int v){ int x,y,z; split(rt,v-1,x,y); split(y,v,y,z); if(!y){ rt=merge(x,z); return; } y=merge(ch[y][0],ch[y][1]); rt=merge(x,merge(y,z)); }` 排名询问权值 v 的排名。将原 Treap 按 v-1 分裂成 x，y 两部分，x 部分的子树大小就是小于 v 的个数，加一就是 v 的排名。 C++ int rk(int v){ int x,y,res; split(rt,v-1,x,y); res=sz[x]+1; rt=merge(x,y); return res; } `int rk(int v){ int x,y,res; split(rt,v-1,x,y); res=sz[x]+1; rt=merge(x,y); return res; }` 第 K 大直接在 Treap 上做类似二分的操作即可。 C++ int kth(int k){ int u=rt; while(1){ if(k `int kth(int k){ int u=rt; while(1){ if(ksz[ch[u][0]]) u=ch[u][0]; else if(k==sz[ch[u][0]]+1) return val[u]; else k-=sz[ch[u][0]]+1,u=ch[u][1]; } }` 前驱、后继根据排名找到对应点即可，可使用前面定义的函数得到。 C++ int pre(int v){ return kth(rk(v)-1); } int suc(int v){ return kth(rk(v+1)); } `int pre(int v){ return kth(rk(v)-1); } int suc(int v){ return kth(rk(v+1)); }` 总代码 C++ #include using namespace std; const int N=2e6; int n,m,rt,idx,last,ans; int ch[N][2],val[N],sz[N],rnd[N]; void pushup(int u){ sz[u]=sz[ch[u][0]]+sz[ch[u][1]]+1; } int newd(int v){ val[++idx]=v,sz[idx]=1,rnd[idx]=rand(); ch[idx][0]=ch[idx][1]=0; return idx; } void split(int u,int key,int &x,int &y){ if(!u){ x=y=0; return; } if(val[u]>n>>m; for(int i=1;i>x; insert(x); } while(m--){ int op,x; cin>>op>>x; x^=last; if(op==1) insert(x); else if(op==2) del(x); else if(op==3) last=rk(x); else if(op==4) last=kth(x); else if(op==5) last=pre(x); else last=suc(x); if(op>=3) ans^=last; } cout `#include using namespace std; const int N=2e6; int n,m,rt,idx,last,ans; int ch[N][2],val[N],sz[N],rnd[N]; void pushup(int u){ sz[u]=sz[ch[u][0]]+sz[ch[u][1]]+1; } int newd(int v){ val[++idx]=v,sz[idx]=1,rnd[idx]=rand(); ch[idx][0]=ch[idx][1]=0; return idx; } void split(int u,int key,int &x,int &y){ if(!u){ x=y=0; return; } if(val[u]key) x=u,split(ch[u][1],key,ch[u][1],y); else y=u,split(ch[u][0],key,x,ch[u][0]); pushup(u); } int merge(int x,int y){ if(!x||!y) return x+y; if(rnd[x]rnd[y]){ ch[x][1]=merge(ch[x][1],y); pushup(x); return x; } else{ ch[y][0]=merge(x,ch[y][0]); pushup(y); return y; } } void insert(int v){ int x,y,u=newd(v); split(rt,v,x,y); rt=merge(merge(x,u),y); } void del(int v){ int x,y,z; split(rt,v-1,x,y); split(y,v,y,z); if(!y){ rt=merge(x,z); return; } y=merge(ch[y][0],ch[y][1]); rt=merge(x,merge(y,z)); } int rk(int v){ int x,y,res; split(rt,v-1,x,y); res=sz[x]+1; rt=merge(x,y); return res; } int kth(int k){ int u=rt; while(1){ if(ksz[ch[u][0]]) u=ch[u][0]; else if(k==sz[ch[u][0]]+1) return val[u]; else k-=sz[ch[u][0]]+1,u=ch[u][1]; } } int pre(int v){ return kth(rk(v)-1); } int suc(int v){ return kth(rk(v+1)); } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); srand(time(0)); cin>>n>>m; for(int i=1;in;i++){ int x; cin>>x; insert(x); } while(m--){ int op,x; cin>>op>>x; x^=last; if(op==1) insert(x); else if(op==2) del(x); else if(op==3) last=rk(x); else if(op==4) last=kth(x); else if(op==5) last=pre(x); else last=suc(x); if(op>=3) ans^=last; } coutans"\n"; return 0; }` P3391 【模板】文艺平衡树与模板平衡树不同的是，文艺平衡树中每个点维护的是其在序列中的位置。当它在序列中位置发生变化是，二叉树的结构也随之变化，但二叉树的中序遍历始终是序列。考虑当序列反转时，我们将反转的部分序列分割出来，相当于这个子树每个左右儿子都要左右调换，但是直接遍历相当于暴力，我们可以利用懒标记，给子树的根打上懒标记，当下次需要遍历子树时再把懒标记下传，维持树的结构。代码： C++ #include using namespace std; const int N=1e5+5; int n,m,rt,idx; int son[N][2],vis[N],siz[N],rnd[N],lazy[N]; void pushup(int u){ siz[u]=siz[son[u][0]]+siz[son[u][1]]+1; } void pushdown(int u){ if(lazy[u]){ swap(son[u][0],son[u][1]); lazy[son[u][0]]=!lazy[son[u][0]]; lazy[son[u][1]]=!lazy[son[u][1]]; lazy[u]=0; } } int newd(int v){ vis[++idx]=v,siz[idx]=1,rnd[idx]=rand(); son[idx][0]=son[idx][1]=0; return idx; } void split(int u,int key,int &x,int &y){ if(!u){ x=y=0; return; } pushdown(u); if(siz[son[u][0]]+1>n>>m; for(int i=1;i>l>>r; solve(l,r); } dfs(rt); return 0; } `#include using namespace std; const int N=1e5+5; int n,m,rt,idx; int son[N][2],vis[N],siz[N],rnd[N],lazy[N]; void pushup(int u){ siz[u]=siz[son[u][0]]+siz[son[u][1]]+1; } void pushdown(int u){ if(lazy[u]){ swap(son[u][0],son[u][1]); lazy[son[u][0]]=!lazy[son[u][0]]; lazy[son[u][1]]=!lazy[son[u][1]]; lazy[u]=0; } } int newd(int v){ vis[++idx]=v,siz[idx]=1,rnd[idx]=rand(); son[idx][0]=son[idx][1]=0; return idx; } void split(int u,int key,int &x,int &y){ if(!u){ x=y=0; return; } pushdown(u); if(siz[son[u][0]]+1key) x=u,split(son[u][1],key-siz[son[u][0]]-1,son[u][1],y); else y=u,split(son[u][0],key,x,son[u][0]); pushup(u); } int merge(int x,int y){ if(!x||!y) return x+y; if(rnd[x]rnd[y]){ pushdown(x); son[x][1]=merge(son[x][1],y); pushup(x); return x; } else{ pushdown(y); son[y][0]=merge(x,son[y][0]); pushup(y); return y; } } void insert(int v){ int x,y,u=newd(v); split(rt,v,x,y); rt=merge(merge(x,u),y); } void solve(int l,int r){ int x,y,z; split(rt,l-1,x,y); split(y,r-l+1,y,z); lazy[y]^=1; merge(merge(x,y),z); } void dfs(int u){ pushdown(u); if(son[u][0]) dfs(son[u][0]); coutvis[u]" "; if(son[u][1]) dfs(son[u][1]); } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); srand(time(0)); cin>>n>>m; for(int i=1;in;i++) insert(i); while(m--){ int l,r; cin>>l>>r; solve(l,r); } dfs(rt); return 0; }` P4402 [CERC2007] robotic sort 机械排序观察题目，当我们每次进行***“找到编号最小的物品的位置 P_1，将区间 [1,P_1] 反转，再找到编号第二小的物品的位置 P_2，将区间 [2,P_2] 反转......”***操作时，较小的物品都会被反转至开头，并且在后续的反转后不会再被操作，所以我们可以视为每次找到当前序列最小值、进行反转操作、并删除它。对于反转而言，不难想到和上题一样打懒标记。但我们要动态求最小并保证序列有序，这和平衡树模板稍有不同，这是就要介绍一个高级科技：笛卡尔树注。笛卡尔树的每个点有两个信息，保证在中序遍历时一个信息与序列一样、同时保证另一个信息在树上形成小根堆。在这我们保证节点编号有序，并使物品大小形成小根堆。这时每次只需求出根左子树的大小并加 1，同时还要加上之前被放在序列开头、被我们忽略的前 i-1 个点。输出答案后对左子树打上懒标记，并把左右子树合并即可。代码： C++ #include using namespace std; #define int long long const int N=2e6; #define lc(x) ch[x][0] #define rc(x) ch[x][1] int n,m,rt,idx,top; int ch[N][2],sz[N],tag[N],st[N],rnd[N]; void pushup(int u){ sz[u]=sz[lc(u)]+sz[rc(u)]+1; } void pushdown(int u){ if(tag[u]){ swap(lc(u),rc(u)); tag[lc(u)]=!tag[lc(u)]; tag[rc(u)]=!tag[rc(u)]; tag[u]=0; } } int merge(int x,int y){ if(!x||!y) return x+y; if(rnd[x]>n; for(int i=1,x;i>x; sz[i]=1,rnd[i]=1*x*(n+1)+i; while(top&&rnd[st[top]]>rnd[i]){ res=st[top--]; pushup(res); } ch[i][0]=res; if(top) ch[st[top]][1]=i; st[++top]=i; } while(top) pushup(st[top--]); rt=st[1]; for(int i=1;i `#include using namespace std; #define int long long const int N=2e6; #define lc(x) ch[x][0] #define rc(x) ch[x][1] int n,m,rt,id…