传送门：点击打开链接
题意：有很多次操作。可以讲区间一部分取出来插入到令一个位置，也能翻转区间
思路：翻转区间和添加删除等区间操作，都是splay的最强大的地方，这题也可以说是splay的一道超级经典的入门题
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;
const int MX = 3e5 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int size[MX];
int num[MX], col[MX], n, m;
int son[MX][2], fa[MX], root, sz;
void Link(int x, int y, int c) {
fa[x] = y; son[y][c] = x;
}
void push_up(int rt) {
size[rt] = size[son[rt][0]] + size[son[rt][1]] + 1;
}
void Reverse(int rt){
col[rt] ^= 1;
swap(son[rt][0], son[rt][1]);
}
void push_down(int rt) {
if(col[rt]) {
Reverse(son[rt][0]);
Reverse(son[rt][1]);
col[rt] = 0;
}
}
void Rotate(int x, int c) {
int y = fa[x];
push_down(y); push_down(x);
Link(x, fa[y], son[fa[y]][1] == y);
Link(son[x][!c], y, c);
Link(y, x, !c);
push_up(y);
}
void Splay(int x, int g) {
push_down(x);
while(fa[x] != g) {
int y = fa[x], cx = son[y][1] == x, cy = son[fa[y]][1] == y;
if(fa[y] == g) Rotate(x, cx);
else {
if(cx == cy) Rotate(y, cy);
else Rotate(x, cx);
Rotate(x, cy);
}
}
push_up(x);
if(!g) root = x;
}
void NewNode(int f, int &rt) {
rt = ++sz;
fa[rt] = f, size[rt] = 1;
son[rt][0] = son[rt][1] = col[rt] = 0;
}
int Select(int k, int g) {
int rt = root;
while(size[son[rt][0]] != k) {
if(size[son[rt][0]] > k) rt = son[rt][0];
else k -= size[son[rt][0]] + 1, rt = son[rt][1];
push_down(rt);
}
Splay(rt, g);
return rt;
}
void Build(int l, int r, int &rt, int f) {
if(l > r) return;
int m = (l + r) >> 1, t;
NewNode(f, rt); num[rt] = m;
Build(l, m - 1, son[rt][0], rt);
Build(m + 1, r, son[rt][1], rt);
push_up(rt);
}
void Prepare(int n) {
sz = 0;
NewNode(0, root); num[1] = 0;
NewNode(root, son[root][1]); num[2] = 0;
Build(1, n, son[2][0], 2);
Splay(3, 0);
}
void Print(int rt, int &DFN){
if(!rt) return;
push_down(rt);
Print(son[rt][0], DFN);
if(num[rt]) printf("%d%c", num[rt], ++DFN == n ? '\n' : ' ');
Print(son[rt][1], DFN);
}
void Flip(int l, int r){
Select(l - 1, 0);
Select(r + 1, root);
Reverse(son[son[root][1]][0]);
}
void Cut(int a, int b, int c){
Select(a - 1, 0);
Select(b + 1, root);
int w = son[son[root][1]][0];
son[son[root][1]][0] = 0;
Splay(son[root][1], 0);
Select(c, 0);
Select(c + 1, root);
son[son[root][1]][0] = w;
Splay(son[root][1], 0);
}
int main(){
//FIN;
while(~scanf("%d%d", &n, &m), n != -1){
Prepare(n);
while(m--){
char op[10]; int a, b, c;
scanf("%s%d%d", op, &a, &b);
if(op[0] == 'C'){
scanf("%d", &c);
Cut(a, b, c);
}else Flip(a, b);
}
int DFN = 0;
Print(root, DFN);
}
return 0;
}