题意：
给定一数组，完成两种操作：
CUT a b c 将区间[a,b]的数删除，并接到新数列的第c个数后面
FLIP a b 将区间[a,b]的数翻转顺序
输出最终的序列
题解：
伸展树的基本操作。
#include<bits/stdc++.h>using namespace std;
#define keyv ch[ch[root][1]][0]
#define ddd puts("111");
const int maxn = 3e5+99;
int n,q;
int pre[maxn],ch[maxn][2],rev[maxn],sz[maxn],key[maxn],root,tot1;void update(int r)
{if(r==0)return;swap(ch[r][0],ch[r][1]);rev[r]^=1;
}void pushdown(int r)
{if(rev[r]){update(ch[r][0]);update(ch[r][1]);rev[r] = 0;}
}void pushup(int r)
{sz[r] = 1 + sz[ch[r][0]] + sz[ch[r][1]];
}
void newnode(int &r,int fa,int k)
{r = ++tot1;pre[r] = fa;key[r] = k;rev[r] = ch[r][0] = ch[r][1] = 0;sz[r] = 1;
}void build(int &x,int l,int r,int fa)
{if(l>r)return;int m = (l+r)>>1;newnode(x,fa,m);build(ch[x][0],l,m-1,x);build(ch[x][1],m+1,r,x);pushup(x);
}void init()
{root = tot1 =0;key[root] = ch[root][0] = ch[root][1] =sz[root] = rev[root] = pre[root] = 0;newnode(root,0,-1);newnode(ch[root][1],root,-1);build(keyv,1,n,ch[root][1]);pushup(ch[root][1]);pushup(root);
}void rotate(int x,int d)
{int y = pre[x];pushdown(y);pushdown(x);ch[y][!d] = ch[x][d];///先搞ypre[ch[x][d]] = y;if(pre[y]) ch[pre[y]][ch[pre[y]][1]==y]=x;///搞xpre[x] = pre[y];ch[x][d] = y;pre[y] = x;pushup(y);
}void splay(int r,int goal)
{while(pre[r] != goal){if(pre[pre[r]]==goal)rotate(r,ch[pre[r]][0]==r);else{int y = pre[r];int d = ch[pre[y]][0]==y;if(ch[y][d]==r){rotate(r,!d);rotate(r,d);}else{rotate(y,d);rotate(r,d);}}}pushup(r);if(goal == 0 )root = r;
}int kth(int r,int k)
{pushdown(r);int t = sz[ch[r][0]];if(k==t+1) return r;else if(k <= t)return kth(ch[r][0],k);else return kth(ch[r][1],k-t-1);
}/**本题操作*/
void cut(int a,int b,int c)
{splay(kth(root,a),0);//a-1后splay(kth(root,b+2),root);//b+1前int tmp = keyv;keyv = 0;pushup(ch[root][1]);pushup(root);splay(kth(root,c+1),0);//c后splay(kth(root,c+2),root);//c+1前keyv = tmp;pre[keyv] = ch[root][1];pushup(ch[root][1]);pushup(root);
}void reverse(int l,int r)
{splay(kth(root,l),0);splay(kth(root,r+2),root);update(keyv);pushup(ch[root][1]);pushup(root);
}int cnt;
void print(int r)
{if(r==0)return;pushdown(r);print(ch[r][0]);if(cnt<n && key[r]>0)///注意加的边界值。{cnt++;printf("%d%c",key[r],cnt==n?'\n':' ');}print(ch[r][1]);}int main()
{while(scanf("%d%d",&n,&q)==2){if(n<0 && q<0)break;init();char op[11];int x,y,z;while(q--){scanf("%s",op);if(op[0]=='C'){scanf("%d%d%d",&x,&y,&z);cut(x,y,z);}else if(op[0]=='F'){scanf("%d%d",&x,&y);reverse(x,y);}cnt=0;}print(root);}
}