【BZOJ】Tyvj 1729 文藝平衡樹 Splay

題目傳送門

好題目，這題讓我們徹底明白了splay和别的平衡樹的差別所在——splay可以支援區間操作！

這題就是一個區間翻轉的裸題，我們可以每次把l-1旋轉到根，把r+1旋轉到根節點的右兒子，不難發現，我們要翻轉的區間就是根的右兒子的左子樹。

然後我們引入和線段樹類似的lazy_tag，記錄目前子樹是否需要翻轉。（因為一個區間連續翻轉兩次顯然和不需要翻轉是一樣的）

每次查詢節點位置和輸出的時候都要把lazy_tag向下push，push也非常簡單，就是把目前子樹的左右子樹交換一下，然後左右子樹的記錄取反一下就行了。

注意：由于可能涉及到區間[1,x]或[x,n]的操作，于是我們可以加入0和n+1這兩個空節點。

p.s.我這裡把[0,n+1]這個區間向後移了一位，變成了區間[1,n+2]了。

附上AC代碼：

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

const int N=1e5+10;
int n,m,size,rt,f[N],w[N],sz[N],ch[N][2],mk[N],x,y;

inline char nc(void){
	static char ch[100010],*p1=ch,*p2=ch;
	return p1==p2&&(p2=(p1=ch)+fread(ch,1,100010,stdin),p1==p2)?EOF:*p1++;
}

inline void read(int &a){
	static char c=nc();int f=1;
	for (;!isdigit(c);c=nc()) if (c=='-') f=-1;
	for (a=0;isdigit(c);a=(a<<3)+(a<<1)+c-'0',c=nc());
	a*=f;return;
}

inline void updata(int x){sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;}

inline void rotate(int x){
	int y=f[x],op=(ch[y][1]==x);
	ch[y][op]=ch[x][op^1];
	if (ch[x][op^1]) f[ch[x][op^1]]=y;
	f[x]=f[y];
	if (f[y]) ch[f[y]][ch[f[y]][1]==y]=x;
	f[y]=x,ch[x][op^1]=y;
	return updata(y),updata(x);
}

inline void splay(int x,int ed){
	for (int fa=f[x]; fa!=ed; rotate(x),fa=f[x])
		if (f[fa]!=ed) rotate((x==ch[fa][0])==(fa==ch[f[fa]][0])?fa:x);
	if (!ed) rt=x;
	return;
}

inline void ist(int x){
	int now=rt;
	while (ch[now][w[now]<x]) now=ch[now][w[now]<x];
	w[++size]=x,f[size]=now,ch[size][0]=ch[size][1]=0;
	if (now) ch[now][w[now]<x]=size;
	return splay(size,0);
}

inline void push(int x){return mk[x]=0,mk[ch[x][0]]^=1,mk[ch[x][1]]^=1,swap(ch[x][0],ch[x][1]);}

inline int pos(int x){
	int now=rt;
	while (now){
		if (mk[now]) push(now);
		if (sz[ch[now][0]]+1>x) now=ch[now][0];
		else if (sz[ch[now][0]]+1==x) return w[now];
		else x-=sz[ch[now][0]]+1,now=ch[now][1];
	}
}

inline void print(int x){
	if (mk[x]) push(x);
	if (ch[x][0]) print(ch[x][0]);
	if (w[x]>1&&w[x]<n+2) printf("%d ",w[x]-1);
	if (ch[x][1]) print(ch[x][1]);
	return;
}

int main(void){
	read(n),read(m);
	for (int i=1; i<=n+2; ++i) ist(i);
	while (m--){
		read(x),read(y);
		x=pos(x),y=pos(y+2);
		splay(x,0),splay(y,x);
		mk[ch[ch[rt][1]][0]]^=1;
	}
	print(rt);
	return 0;
}