BZOJ 3223 文艺平衡树

题目大意

请维护一个有序数列，支持对区间的翻转。

暴力！23333

这题因为翻转操作很多，当然不能用暴力……

之后发现是区间翻转问题，直接上Splay就好了。

#include <cstdio>
#include <algorithm>
using namespace std;

#define N 100010

int n,m,rt,c[2][N],fa[N],siz[N],l,r;
bool rev[N];

void pushup(int pos){siz[pos]=siz[c[0][pos]]+siz[c[1][pos]]+1;}

inline void pushdown(int pos)
{
	if(rev[pos])
	{
		rev[c[0][pos]]^=1,rev[c[1][pos]]^=1;
		swap(c[0][c[0][pos]],c[1][c[0][pos]]);
		swap(c[0][c[1][pos]],c[1][c[1][pos]]);
		rev[pos]=false;
	}
}

int build(int l,int r)
{
	if(l>r) return 0;
	int mid=(l+r)>>1;
	c[0][mid]=build(l,mid-1),fa[c[0][mid]]=mid;
	c[1][mid]=build(mid+1,r),fa[c[1][mid]]=mid;
	pushup(mid);
	return mid;
}

void DFS(int pos)
{
	pushdown(pos);
	if(c[0][pos]) DFS(c[0][pos]);
	if(pos!=1&&pos!=n+2) printf("%d ",pos-1);
	if(c[1][pos]) DFS(c[1][pos]);
}

void rotate(int &tg,int tx)
{
	int ty=fa[tx],tz=fa[ty],tl=(c[1][ty]==tx),tr=tl^1;
	if(ty==tg) tg=tx;
	else c[c[1][tz]==ty][tz]=tx;
	fa[tx]=tz,fa[ty]=tx;
	fa[c[tr][tx]]=ty,c[tl][ty]=c[tr][tx],c[tr][tx]=ty;
	pushup(ty),pushup(tx);
}

void splay(int &tg,int tx)
{
	while(tx!=tg)
	{
		int ty=fa[tx],tz=fa[ty];
		if(ty!=tg)
		{
			if((c[0][ty]==tx)^(c[0][tz]==ty)) rotate(tg,tx);
			else rotate(tg,ty);
		}
		rotate(tg,tx);
	}
}

int lookfor(int pos,int tg)
{
	pushdown(pos);
	if(tg<=siz[c[0][pos]]) return lookfor(c[0][pos],tg);
	if(tg>siz[c[0][pos]]+1) return lookfor(c[1][pos],tg-siz[c[0][pos]]-1);
	return pos;
}

int main()
{
	scanf("%d%d",&n,&m);
	rt=build(1,n+2);
	while(m--)
	{
		scanf("%d%d",&l,&r);
		l++,r++;
		splay(rt,lookfor(rt,l-1)),splay(c[1][rt],lookfor(rt,r+1));
		swap(c[0][c[0][c[1][rt]]],c[1][c[0][c[1][rt]]]);
		rev[c[0][c[1][rt]]]^=1;
	}
	DFS(rt);
	return 0;
}