splay详细注释
#include<bits/stdc++.h>
using namespace std;
const int N =1e5+10;
int n,m;
struct node
{
int s[2],p,v;//s表示左右儿子,p是父节点,v是值
int size,flag;
void init(int _v,int _p)
{
v=_v,p=_p;
size=1;
}
}tr[N];
int root,idx;
void pushup(int x)
{
tr[x].size=tr[tr[x].s[0]].size+tr[tr[x].s[1]].size+1;
}
void pushdown(int x)
{
if(tr[x].flag)
{
swap(tr[x].s[0],tr[x].s[1]);//交换左右儿子
tr[tr[x].s[0]].flag^=1;//标记
tr[tr[x].s[1]].flag^=1;//标记
tr[x].flag=0;
}
}
void rotate(int x)
{
int y=tr[x].p,z=tr[y].p;//x的父节点y,y的父节点z
int k=tr[y].s[1]==x;//k=0,表示x是y的左儿子,k=1表示x是y的右儿子
tr[z].s[tr[z].s[1]==y]=x,tr[x].p=z;//以右旋为例子,则k=0
//此时z连接的本来的y儿子要更新为x,tr[z].s[1]==y表示y是z的左儿子还是右儿子
//然后x的父节点更新为z
tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;//y的左儿子k=0,等于
//本来x的右儿子;x的右儿子现在是y的儿子
tr[x].s[k^1]=y,tr[y].p=x;//x的右儿子k=0等于y
pushup(y),pushup(x);//先x的儿子y,而后x
}
void splay(int x,int k)//将x旋转到k下面
{
while(tr[x].p!=k)//x的父节点不是k,也就至少两层
{
int y=tr[x].p,z=tr[y].p;//y是x的父节点,z是y的父节点
if(z!=k)
{
if((tr[y].s[1]==x)^(tr[z].s[1]==y)) rotate(x);//折线先转x
else rotate(y); //直线先转y
}
rotate(x);//if(z==k)只需要转一次x就可以啦
}
if(!k) root=x;//k=0是根节点,直接把root给根节点
}
void ins(int v)
{
int u=root,p=0;
while(u) p=u,u=tr[u].s[v>tr[u].v];//找到v应该插入的地方
u=++idx;//记录是第几个插入的点
if(p) tr[p].s[v>tr[p].v]=u;//将u插入到p的儿子如果p==0,那么u=1.
tr[u].init(v,p);//初始化
splay(u,0);//将u旋转到根节点
}
int get_k(int k)
{
int u=root;
while(true)
{
pushdown(u);//因为查第几个数是查操作后的数,得先把flag传下去
if(tr[tr[u].s[0]].size>=k) u=tr[u].s[0];//tr[tr[u].s[0]].size表示左儿子得节点数
//大于等于k说明在左子树里
else if(tr[tr[u].s[0]].size+1>=k) return u;//由于没有执行tr[tr[u].s[0]].size>=k
//说明tr[tr[u].s[0]].size<k,但是tr[tr[u].s[0]].size+1>=k,表明第k个数就是u;
else k-=tr[tr[u].s[0]].size+1,u=tr[u].s[1];//否则在右子树里
}
return -1;
}
void output(int u)
{
pushdown(u);//递归之前先传懒标记
if(tr[u].s[0]) output(tr[u].s[0]);//左子树存在先遍历
if(tr[u].v>=1&&tr[u].v<=n) printf("%d ",tr[u].v);//因为有哨兵,所以得判断是不是哨兵
if(tr[u].s[1]) output(tr[u].s[1]);//遍历右子树
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<=n+1;i++) ins(i);
while(m--)
{
int l,r;
scanf("%d%d",&l,&r);
l=get_k(l),r=get_k(r+2);
//由于我们加了左右边界,要删除的序列应该是[l+1,r+1],
//所以要处理l和r+2;
splay(l,0),splay(r,l);//将l转到根节点,r转到l的后继节点
tr[tr[r].s[0]].flag^=1;//r的左儿子翻转,左儿子就是我们的序列
}
output(root);//输出中序遍历
return 0;
}
fhq Treap
#include<bits/stdc++.h>
using namespace std;
const int N =100010;
struct node
{
int l,r;
int sz,key,val;
int flag;
}tr[N];
int root,idx;
int get_node(int key)
{
int u=++idx;
tr[u].key=key;
tr[u].val=rand();
tr[u].sz=1;
return u;
}
void pushup(int u)
{
tr[u].sz=tr[tr[u].l].sz+tr[tr[u].r].sz+1;
}
void pushdown(int u)
{
if(tr[u].flag)
{
swap(tr[u].l,tr[u].r);
tr[tr[u].l].flag^=1,tr[tr[u].r].flag^=1;
tr[u].flag=0;
}
}
void split(int u,int sz,int &x,int &y)
{
if(!u) x=y=0;
else
{
pushdown(u);
if(tr[tr[u].l].sz<sz)
{
x=u;
split(tr[u].r,sz-tr[tr[u].l].sz-1,tr[u].r,y);
}
else
{
y=u;
split(tr[u].l,sz,x,tr[u].l);
}
pushup(u);
}
}
int merge(int x,int y)//merge的顺序不能写反
{
if(!x||!y) return x+y;
if(tr[x].val>tr[y].val)
{
pushdown(x);
tr[x].r=merge(tr[x].r,y);
pushup(x);
return x;
}
else
{
pushdown(y);
tr[y].l=merge(x,tr[y].l);
pushup(y);
return y;
}
}
void rever(int l,int r)
{
int x,y,z;
split(root,l-1,x,y);
split(y,r-l+1,y,z);
tr[y].flag=1;
root=merge(merge(x,y),z);
}
void dfs(int u)
{
if(!u) return;
pushdown(u);
dfs(tr[u].l);
printf("%d ",tr[u].key);
dfs(tr[u].r);
}
int main()
{
int n,m;
scanf("%d%d", &n, &m);
for(int i=1;i<=n;i++) root=merge(root,get_node(i));
while (m -- )
{
int l,r;
scanf("%d%d", &l, &r);
rever(l,r);
}
dfs(root);
return 0;
}
请问这道题旋转的时候不用考虑懒标记的变化吗