题目链接HDU3487
【题意】给出一个长度为n的序列，初始化为{1,2,3…n}

有两种操作:

CUT a b c     :把[a,b]剪切出来，[1,a-1]+[b+1,n]合并起来形成新序列，把剪切出来的[a,b]放在新序列的第c个后面；

FLIP a b       :倒转[a,b]

最后输出最终序列；

【分析】标准的splay，加上lazy标记就好了。

【AC CODE】499ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
//#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 3*100000+10;
/* 从下往上伸展的splay */
struct NODE{
	NODE *ch[2], *fa;
	int sz,v;//sz-当前子树有多少个结点,v-结点值
	bool f;//lazy标记
	int chd(){//当前结点是左儿子还是右儿子,返回0-左儿子,1-右儿子
		return this == fa->ch[1];
	}
	void push_up(){
		sz = ch[0]->sz+ch[1]->sz+1;
	}
	void push_down(){
		if(f){
			f = false;
			swap(ch[0],ch[1]);
			ch[0]->f ^= 1;
			ch[1]->f ^= 1;
		}
	}
};
NODE *null = new NODE;
inline void setch(NODE *fa, NODE *u, int p)//重置关联的儿子和父亲,p=0表示u是fa的左儿子1是右儿子
{
	fa->ch[p] = u, u->fa = fa;
}
void rot(NODE *u)//旋转
{
	NODE*y = u->fa;
	int d = u->chd();//决定是左旋还是右旋d=0左儿子对应右旋,d=1右儿子对应左旋
	setch(y->fa,u,y->chd());//把y的父亲(就是u父亲的父亲)的y儿子变为u =====把u放到当前根
	setch(y,u->ch[d^1],d);//把u的对应儿子放到u所在位置(此时变成两颗树了 y成另外一颗树的根)
	setch(u,y,d^1);//把y放到u的对应儿子
	y->push_up(), u->push_up();//先更新y再更新u(y在u下面了)
}
/* =================== splay1->start ===========================================*/
void dfs_down(NODE *x)//先把根到x所用到的所有的标记下放
{
	if(x == null)return;
	dfs_down(x->fa);
	x->push_down();//保证从上往下push_down
}
void splay(NODE* &rt,NODE *x, NODE *p)//把rt树的x节点伸展到p下方(即p的儿子),从下往上伸展
{
	dfs_down(x);
	if(x == p) return;
	while(x->fa != p)
	{
		NODE *y = x->fa;
		if(x->fa->fa != p && x->chd() == y->chd()) rot(y);
		rot(x);
	}
	if(p == null) rt = x;
}
/* =================== splay1->end ===========================================*/
/* =================== splay2->start ===========================================*/
NODE* find_kth(NODE *u, int k)//寻找第k小的结点(数列从左往右第k个),u为splay的根
{
	u->push_down();
	int d = k - u->ch[0]->sz;
	if(1 == d) return u;//找到
	if(d <= 0) return find_kth(u->ch[0],k);//往左
	return find_kth(u->ch[1],k-u->ch[0]->sz-1);//往右
}
void splay(NODE* &rt,int k, NODE *p)//把rt树第k大结点(数列从左往右第k个)伸展到p下面
{
	NODE *x = find_kth(rt,k);
	if(x == p) return;
	while(x->fa != p)
	{
		NODE *y = x->fa;
		if(x->fa->fa != p && x->chd() != y->chd()) rot(y);
		rot(x);
	}
	if(p == null) rt = x;
}
/* =================== splay2->end ===========================================*/
void del(NODE* &rt,NODE *x)//删除rt树的结点x
{
	NODE *u = x->ch[0], *v = x->ch[1];
	if(null == u) setch(null,v,1);//如果没有左儿子就把右儿子设为根
	else if(null == v) setch(null,u,1);//没有左儿子就把左儿子设为根,左右都没的话就变成空树了
	else
	{
		//左右儿子都存在时分别找出x左边和x右边的结点
		u->push_down(), v->push_down();
		while(u->ch[1] != null){u = u->ch[1], u->push_down();}
		while(v->ch[0] != null){v = v->ch[0], v->push_down();}
		//把x左边的u伸展到根，把x右边的v伸展到u下面
		splay(rt,u,null), splay(rt,v,u);
		v->ch[0] = null;
	}
}
/*合并left和right，假定left所有元素都比right小；right可以是NULL，但left不可以*/
NODE* merge(NODE *left, NODE *right)
{
	splay(left,left->sz,null);//把left中序顺序最后一个结点 伸展到根,这样left就没有右子树了
	setch(left,right,1);//把right接到left的右子树
	left->push_up();//更新根节点需要维护的值
	return left;
}
/*分裂rt,把rt前k小结点放在left,其他放在right; 1<= k <=rt->sum当k==rt->sum时right=NULL,rt不能空*/
void split(NODE* &rt, int k, NODE* &left, NODE* &right)
{
	splay(rt,k,null);//把rt的第k小的结点伸展到u的根
	right = rt->ch[1];//rt的右儿子就是right
	right->fa = null;//right的fa需要变为null
	left = rt;//rt的左儿子以及rt就是left，右儿子改为null
	rt->ch[1] = null;
	left->push_up();//只需要更新左儿子，右儿子不需要更新
}
/*修改[x,y]的值,lazy标记,rt != NULL,把x-1伸展到根，y+1伸展到根的右儿子，那么根的右儿子的左儿子就是区间[x,y]，这里左右各增加了一个虚拟节点方便处理*/
void update(NODE* &rt, int x, int y)
{
	splay(rt,x-1,null);
	splay(rt,y+1,rt);
	rt->ch[1]->ch[0]->f ^= 1;
}
struct SplayTree{
	NODE node[MAXN];
	NODE *rt;
	void bulid(NODE* &u, int x, int y, NODE *fa)
	{
		if(x > y)
		{
			u = null;
			return;
		}
		int m = (x+y)>>1;
		u = &node[m];
		u->f = 0;
		u->fa = fa;
		u->v = m;
		bulid(u->ch[0],x,m-1,u);
		bulid(u->ch[1],m+1,y,u);
		u->push_up();
	}
	void init(int sz)
	{
		null->sz = 0;
		null->fa = NULL;
		bulid(rt,0,sz+1,null);//这里左右各加了一个虚拟结点
	}
}s;
void debug(NODE *u)
{
	if(u == null) return;
	u->push_down();
	debug(u->ch[0]);
	printf("%d\n", u->v);
	debug(u->ch[1]);
}
vector<int> ans;
void pt(NODE *u)
{
	if(u == null) return;
	u->push_down();
	pt(u->ch[0]);
	ans.push_back(u->v);
	pt(u->ch[1]);
}

int main()
{
#ifdef SHY
    freopen("e:\\1.txt", "r", stdin);
#endif
    int n,m;
	while(~scanf("%d %d%*c", &n, &m) && ~n)
	{
		char op[10];
		int a,b;
		s.init(n);
		rep(i,0,m)
		{
			scanf("%s %d %d%*c", op, &a, &b);
			if('C' == op[0])
			{
				int c;
				scanf("%d%*c", &c);
				NODE *left,*mid,*right,*u;
				//剪切出[a,b]
				split(s.rt,a,left,u);
				split(u,b-a+1,mid,right);
				//合并出新序列
				u = merge(left,right);
				//把[a,b]插入第c个后面
				split(u,c+1,left,right);
				s.rt = merge(merge(left,mid),right);
			}
			else
				update(s.rt,a+1,b+1);
		}
		ans.clear();
		pt(s.rt);
		printf("%d", ans[1]);
		repe(i,2,n) printf(" %d", ans[i]);
		putchar('\n');
	}
    return 0;
}