Ryan_<

1、理解树中节点的含义以及节点所记录的信息：

每个节点的值即为该节点的编号 故用id[]储存信息(这道题是给出的是1~n的有序数列，满足id[i]==i 故可省略id[])

  建树：不用Splay Tree的插入旋转操作，普通的二分建树即可

void build(int l,int r,int k)
{
	if(l>r) return;
	/*这个是必要的
	可以模拟建树过程
		/*get嵌套注释~
		i     7   3
		id[i] 1   2
		/
		1   2
	上述情况就会用到该语句
	*/
	int now=id[l],last=id[k];
	if(l==r)
	{
		fa[now]=last;
		s[now]=1;
		if(l<k)
			tr[last][0]=now;
		else
			tr[last][1]=now;
		return;
	}
	int mid=l+r>>1;
	now=id[mid];
	build(l,mid-1,mid);	build(mid+1,r,mid);//mid为根，左右建树
//===l>r return后到这里将未加入的节点加入mid
	fa[now]=last;
	pushup(mid);

	if(mid<k)//比较值 故不是now和last
		tr[last][0]=now;
	else tr[last][1]=now;
}

2、区间翻转操作：

Splay处理区间[l,r]，将l-1转至根部，将r+1转至根的右孩子，这样根的右孩子的左子树便为[l,r]。

为了处理l==1||r==n的情况，新增两个节点 0,n+1。方便起见，将所有节点的编号加1。则在树中插入节点为1到n+2  节点1和节点n+2是没有意义的

int find(int p,int rank)
{
	pushdown(p);
	int l=tr[p][0],r=tr[p][1];
	if(s[l]+1==rank) return p;
	else if(s[l]>=rank) return find(l,rank);//返回l即可，不用tr[p][0]
	else return find(r,rank-s[l]-1);
}
void rever(int l,int r)
{
	int x=find(rt,l),y=find(rt,r+2);
	splay(x,rt);
	splay(y,tr[x][1]);
	int z=tr[y][0];
	rev[z]^=1;//标记
}

3、Rotate操作：旋转四步走

void rotate(int x,int &p)
{
	int y=fa[x],z=fa[y];
	int l,r;
	if(tr[y][0]==x) l=0;
	else l=1;
	r=l^1;
	//===换根===/
	if(y==p)
		p=x;
	else
	{
		if(tr[z][0]==y) tr[z][0]=x;
		else tr[z][1]=x;
	}
	//===换父亲===/
	fa[x]=z;fa[y]=x;
	fa[tr[x][r]]=y;
	//===换儿子===/
	tr[y][l]=tr[x][r];
	tr[x][r]=y;
	//===更新所维护的值（顺序随意）/
	pushup(y);pushup(x);
}

其中if(y==p) p=x;

注意这里表示单旋或双旋第二步的操作。此时z并非第一步时的z，而是y旋转到根后新的父节点。正如第一行 z=fa[y] 这里的z是变化的。当然随着旋转,y所指结点也可能变化。

4、 update(p)操作：对以p为根的树进行更新

根据更新的方向分为pushup()和pushdown()

pushup()为从下向上更新

pushdown()为从上向下更新

本来更新操作放函数中即可，单另出来便于之后维护更多属性。

我的代码：

#include<cstdio>
#include<iostream>
#include<cstdlib>
#define for2(i,s,t) for(int i=(s);i<=(t);i++)
using namespace std;
const int M=100000+10;
int n,m,rt,tot;
int tr[M][2],id[M],fa[M],s[M];
bool rev[M];
inline void pushup(int p)
{
	int l=tr[p][0],r=tr[p][1];
	s[p]=s[l]+s[r]+1;
}
inline void pushdown(int p)
{
	int l=tr[p][0],r=tr[p][1];
	if(rev[p])
	{
		swap(tr[p][0],tr[p][1]);
		rev[l]^=1;rev[r]^=1;
		rev[p]=0;
	}
}
void rotate(int x,int &p)
{
	int y=fa[x],z=fa[y];
	int l,r;
	if(tr[y][0]==x) l=0;
	else l=1;
	r=l^1;
	if(y==p)
		p=x;
	else
	{
		if(tr[z][0]==y) tr[z][0]=x;
		else tr[z][1]=x;
	}
	fa[x]=z;fa[y]=x;
	fa[tr[x][r]]=y;
	tr[y][l]=tr[x][r];
	tr[x][r]=y;
	pushup(y);pushup(x);
}
void splay(int x,int &p)
{
	while(x!=p)
	{
		int y=fa[x],z=fa[y];
		if(y!=p)
		{
			if((tr[y][0]==x)^(tr[z][0]==y))
				rotate(x,p);
			else
				rotate(y,p);
		}
		rotate(x,p);
	}
}
void build(int l,int r,int k)
{
	if(l>r) return;
	int now=id[l],last=id[k];
	if(l==r)
	{
		fa[now]=last;
		s[now]=1;
		if(l<k)
			tr[last][0]=now;
		else
			tr[last][1]=now;
		return;
	}
	int mid=l+r>>1;
	now=id[mid];
	build(l,mid-1,mid);	build(mid+1,r,mid);
	fa[now]=last;
	pushup(mid);
	if(mid<k)
		tr[last][0]=now;
	else tr[last][1]=now;
}
int find(int p,int rank)
{
	pushdown(p);
	int l=tr[p][0],r=tr[p][1];
	if(s[l]+1==rank) return p;
	else if(s[l]>=rank) return find(l,rank);
	else return find(r,rank-s[l]-1);
}
void rever(int l,int r)
{
	int x=find(rt,l),y=find(rt,r+2);
	splay(x,rt);
	splay(y,tr[x][1]);
	int z=tr[y][0];
	rev[z]^=1;
}
int main()
{
	scanf("%d%d",&n,&m);
	for2(i,1,n+2) id[i]=++tot;
	build(1,n+2,0);
	rt=(n+3)>>1;
	for2(i,1,m)
	{
		int L,R;
		scanf("%d%d",&L,&R);
		rever(L,R);
	}
	for2(i,2,n+1)
		printf("%d ",find(rt,i)-1);
	return 0;
}