SplayTree

2019-11-14 12:11:05

字体：大中小

来源：转载

供稿：网友

Splay是个好东西，中文译名为伸展树，它除了拥有Treap的功能外，还也可以实现快速分裂和合并序列。（学之前最好先对BST和Treap有一定了解）最重要的是理解Splay的伸展操作，即将一个指定节点x自底向上通过旋转操作，使x成为根节点，要分三种情况来考虑： 1、x的节点为父节点，进行一次单旋即可； 2、x的父节点y、y的父节点z在一条直线上如下图：这里写图片描述 3、x,y,z不在一条直线上，形成一个“Z”形如下图：（好吧图确时有点那个啥，不过这不是重点，理解就好）上代码：

//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