P3391 【模板】文艺平衡树 - 华师一附中OI组

#include<bits/stdc++.h>
using namespace std;
const int inf=0X3FFFFFFF;
const int N=100100;
struct node
{
int val,fa,s[2],sz,rev;
} a[N];
int n, tot, root;
void ArrayPr()
{
cout<<endl<<" i ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
cout<<endl<<"val ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
cout<<endl<<" s0 ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[0];
cout<<endl<<" s1 ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[1];
cout<<endl<<" fa ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].fa;
cout<<endl<<" sz ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].sz;
cout<<endl<<"rev ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].rev;
cout<<endl;
}
void pushdown(int rt)
{
if (rt==0) return ;
int R=a[rt].rev;
int l=a[rt].s[0], r=a[rt].s[1];
if (R>0)
{
a[rt].s[0]=r,a[rt].s[1]=l;
a[rt].rev=0;
if (l>0)a[l].rev^=1;
if (r>0)a[r].rev^=1;
}
}
void pushup(int rt)
{
int l=a[rt].s[0], r=a[rt].s[1];
a[rt].sz=a[l].sz+a[r].sz+1;
}
void BSTPr(int rt)
{
if (rt>0)
{
BSTPr(a[rt].s[0]);
cout<<a[rt].val<<' ';
BSTPr(a[rt].s[1]);
}
}
int Son(int x)
{
int y=a[x].fa;
return a[y].s[1]==x;
}
void R(int x)
{
int y=a[x].fa;
int z=a[y].fa;
pushdown(y),pushdown(x);///下传
int k=Son(x);
int v=a[x].s[k^1];
a[y].s[k]=v,a[v].fa=y;///v挂在y下
a[z].s[Son(y)]=x,a[x].fa=z;///x挂在z下
a[x].s[k^1]=y,a[y].fa=x;///y挂在x下
pushup(y),pushup(x);///上传
}
inline void Splay(int x,int rt=root)
{
rt=a[rt].fa;
int y,z;
while(a[x].fa!=rt)
{
y=a[x].fa,z=a[y].fa;;
if(z!=rt)
if(Son(x)==Son(y))R(y);
else R(x);
R(x);
}
if(rt==0)root=x;
}
int Getkth(int rt,int k) ///第k个的数的位置
{
pushdown(rt);
int l=a[a[rt].s[0]].sz; /// RT的左儿子下的个数
if(l+1==k) return rt;
if(l+1>k) return Getkth(a[rt].s[0], k); ///左儿子里去找
if(l+1<k) return Getkth(a[rt].s[1], k-(l+1));
}
int Build(int l,int r)
{
if (l>r) return 0;
if (l==r)
{
a[l].val=l-1;
a[l].sz=1;
return l;
}
int m=(l+r)/2;
int L=a[m].s[0]=Build(l,m-1);
int R=a[m].s[1]=Build(m+1,r);
a[m].sz=r-l+1;
a[m].val=m-1;
a[L].fa=a[R].fa=m;
return m;
}
void Get(int x,int y) ///把第x个转到根，y转到x的右子树
{
int l=Getkth(root,x);
int r=Getkth(root,y);
Splay(l,root);
Splay(r,a[root].s[1]);
}
int main()
{
int m,x,opt,L,R,V;
cin>>n>>m;
///初始建树
tot=n+2;
root=Build(1,tot);
while(m--)
{
cin>>L>>R;
Get(L,R+2);
int t=a[root].s[1];
t=a[t].s[0];
a[t].rev^=1;
}
Get(1,n+2);
int t=a[root].s[1];
t=a[t].s[0];
BSTPr(t);
return 0;
}
/*
5 3
1 3
1 3
1 4
*/

复制代码