SplayTree

2019-11-14 12:10:14

字體：大中小

供稿：網(wǎng)友

Splay是個(gè)好東西，中文譯名為伸展樹，它除了擁有Treap的功能外，還也可以實(shí)現(xiàn)快速分裂和合并序列。（學(xué)之前最好先對(duì)BST和Treap有一定了解）最重要的是理解Splay的伸展操作，即將一個(gè)指定節(jié)點(diǎn)x自底向上通過旋轉(zhuǎn)操作，使x成為根節(jié)點(diǎn)，要分三種情況來考慮： 1、x的節(jié)點(diǎn)為父節(jié)點(diǎn)，進(jìn)行一次單旋即可； 2、x的父節(jié)點(diǎn)y、y的父節(jié)點(diǎn)z在一條直線上如下圖：這里寫圖片描述 3、x,y,z不在一條直線上，形成一個(gè)“Z”形如下圖：（好吧圖確時(shí)有點(diǎn)那個(gè)啥，不過這不是重點(diǎn)，理解就好）上代碼：

//codevs2048#include <cstdio>#include <algorithm>#define maxn 100000+5using namespace std;int num,n,l,r,m,root,x,hh,ll,rr,mid,o;struct xx{ int ch[2],r,v,flag,sz;}a[maxn];int cmp(int t,int x){ hh=a[a[t].ch[0]].sz+1; if (hh==x) return -1; return x<hh?0:1; }void pushdown(int t){ if (a[t].flag) { a[t].flag=0; swap(a[t].ch[0],a[t].ch[1]); a[a[t].ch[0]].flag^=1; a[a[t].ch[1]].flag^=1; }}void maintain(int t){ a[t].sz=a[a[t].ch[0]].sz+a[a[t].ch[1]].sz+1;}void rotate(int &t,int d){ int k=a[t].ch[d^1]; a[t].ch[d^1]=a[k].ch[d]; a[k].ch[d]=t; a[k].sz=a[t].sz; maintain(t); t=k;}void insert(int &t,int x){ if (!t){a[t=++num]=(xx){0,0,rand(),x,0,1};return ;} a[t].sz++; insert(a[t].ch[1],x); if (a[a[t].ch[1]].r>a[t].r)rotate(t,0);}void splay(int &t,int k){ pushdown(t); int d=cmp(t,k); if (d==1) k-=a[a[t].ch[0]].sz+1; if (d!=-1) { int p=a[t].ch[d]; pushdown(p); int d2=cmp(p,k); int k2=(d2==0?k:k-a[a[p].ch[0]].sz-1); if (d2!=-1) { splay(a[p].ch[d2],k2);//not splay(p,k2)!!!!! if (d==d2) rotate(a[t].ch[d],d^1); else rotate(a[t].ch[d],d); } rotate(t,d^1); }}//合并 void _merge(int &left,int &right){ splay(left,a[left].sz); a[left].ch[1]=right; maintain(left); root=left;}//分裂 void split(int &t,int k,int &left,int &right){ splay(t,k); left=t; right=a[t].ch[1]; a[t].ch[1]=0; maintain(t);}void PRint(int t){ if (!t) return ; pushdown(t); print(a[t].ch[0]); if (a[t].v!=-23333333)printf("%d ",a[t].v); print(a[t].ch[1]);}int main(){ scanf("%d%d",&n,&m); insert(root,-23333333); for (int i=0;i<n;i++) scanf("%d",&x),insert(root,x); while (m--) { scanf("%d%d",&l,&r); split(root,l,ll,o); split(o,r-l+1,mid,rr); a[mid].flag^=1; _merge(ll,mid); _merge(root,rr); } print(root); return 0; }

這里寫圖片描述 hhh