[Splay]模板

[源代码地址](https://www.luogu.org/blog/teafrogsf/stdplay) 我想给他做个注释。 ```cpp #include<iostream> #include<cstring> #include<cstdio> #define swap(a,b) (a)==(b)?1:(a)^=(b)^=(a)^=(b)//翻转 #define neko 1000010 typedef int arr[neko]; int son[neko][2],n,m,p,root; arr fa,siz,ord,rev; inline void read(int &x)//读优 { char c=getchar();x=0; while(!isdigit(c)){if(c=='-')p=-1;c=getchar();} while(isdigit(c)) { x=(x<<1)+(x<<3)+(c^'0'); c=getchar(); } } inline bool get(int x)//判断左儿子还是右儿子 {return son[fa[x]][1]==x;} inline void pushup(int x)//上推更新 { if(x) siz[x]=siz[son[x][0]]+siz[son[x][1]]+1; } void pushdown(int root)//下推翻转 { if (rev[root]){ rev[son[root][0]]^=1;//标记两个儿子 rev[son[root][1]]^=1; rev[root]=0;//清0 swap(son[root][0],son[root][1]);//交换两个儿子 } } void edit(int x,int fat)//增加节点 { ++p; son[p][0]=son[p][1]=0;//son初始化 fa[p]=fat,siz[p]=1;//此时没有儿子所以size为1，标记一下父亲节点 ord[p]=x;//存储真实值 } inline void rotate(int x)//旋转操作 { int y=fa[x],z=fa[y];//z为x爷爷 bool side=get(x);//side表示x在哪边 son[y][side]=son[x][side^1],fa[son[y][side]]=y;//将x的儿子给y，标记父亲儿子 son[x][side^1]=y,fa[y]=x,fa[x]=z;//x来做y的父亲 if(z)son[z][son[z][1]==y]=x;pushup(y);pushup(x);//这里为什么先更新y呢，因为这时候y已经成为了x的儿子 } inline void splay(int x,int tag)//双旋Splay { for(register int y;(y=fa[x])!=tag;rotate(x))//如果没到目标根位置，就旋一下 if(fa[y]!=tag) rotate((get(x)^get(y))?x:y);//如果还是没到根就再旋一下 if(tag==0) root=x;//更新根 } inline void insert(int x)//增加一个值为x的节点 { if(root==0){//如果是根就直接丢入 edit(x,0); root=p; return; } int now=root,fat=0; while(1){ fat=now,now=son[now][ord[now]<x]; if(now==0){ edit(x,fat);//增加节点 son[fat][ord[fat]<x]=p;//丢到now后面，根据大小选择左右子树 pushup(fat);//更新一下 splay(p,0);//插入节点时需要平衡一下排序树 break; } } } inline int query(int x)//询问 { int now=root; while(1){ pushdown(now); if(x<=siz[son[now][0]]) now=son[now][0];//x在左子树上 else{//此时x大于他左子树的大小，即一定不在左子树上 int tmp=siz[son[now][0]]+1;//tmp定义为左子树与本身的大小 if(x<=tmp)return now;//如果此时tmp大小刚好等于左子树，即已经找到位置，就返回 else x-=tmp,now=son[now][1];//否则他就在右子树上，并且此时的x减少左子树和本身的数量 } } } void update(int x,int y) { int l=query(x),r=query(y+2); //x实际上已经是前驱，y+2实际上就是后继 splay(l,0),splay(r,l);//将这个区间旋转出来 rev[son[son[root][1]][0]]^=1; //将旋转出来的区间作上翻转标记 } void inorder(int root){//中序遍历 pushdown(root);//翻转一次 if(son[root][0]) inorder(son[root][0]);//遍历左子树 if(ord[root]>1&&ord[root]<=n+1) printf("%d ",ord[root]-1);//如果当前节点不是边界就输出 if(son[root][1]) inorder(son[root][1]);//遍历右子树 } int main(){ int x,y; scanf("%d%d",&n,&m); for(register int i=1;i<=n+2;i=-(~i)) insert(i);//左边界，右边界 for(register int i=1;i<=m;i=-(~i)){ read(x); read(y); update(x,y);//翻转操作 } inorder(root);//输出一遍 putchar('\n'); return 0; } ```