这种高级数据结构太难搞了.........现在还是先照着别人的代码敲，做模板..........慢慢花时间来弄懂
#include#include #include #include #include #include #include #include #include #include #include #include //形如INT_MAX一类的#define MAX 301111#define INF 0x7FFFFFFF#define REP(i,s,t) for(int i=(s);i<=(t);++i)#define ll long long#define mem(a,b) memset(a,b,sizeof(a))#define mp(a,b) make_pair(a,b)#define LL(x) x<<1#define RR(x) x<<1|1# define eps 1e-5//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂using namespace std;int n,q,root,tot,cnt;int size[MAX],ch[MAX][2],key[MAX],pre[MAX],num[MAX],lazy[MAX],node[MAX];void newnode(int &x, int va,int fa) { x = ++ tot; ch[x][0] = ch[x][1] = 0; pre[x] = fa; lazy[x] = 0; key[x] = va;}void up(int x) { size[x] = size[ch[x][0]] + size[ch[x][1]] + 1;}void down(int x) { if(lazy[x]) { swap(ch[x][0],ch[x][1]); lazy[ch[x][0]] ^= 1; lazy[ch[x][1]] ^= 1; lazy[x] = 0; }}void build(int &x,int L,int R,int fa) { if(L > R) return ; int mid = (L + R) >> 1; newnode(x,mid,fa); build(ch[x][0],L,mid-1,x); build(ch[x][1],mid+1,R,x); up(x);}void init() { root = tot = 0; ch[0][0] = ch[0][1] = pre[0] = lazy[0] = size[0] = 0; newnode(root,-1,0); newnode(ch[root][1],-1,root); size[root] = 2; build(ch[ch[root][1]][0],1,n,ch[root][1]); up(ch[root][1]); up(root);}void rotate(int x,int kind) { // 0 :左旋 1：右旋 int y = pre[x]; down(y); down(x); ch[y][!kind] = ch[x][kind]; pre[ch[x][kind]] = y; if(pre[y]) ch[pre[y]][ch[pre[y]][1] == y] = x; pre[x] = pre[y]; ch[x][kind] = y; pre[y] = x; up(y);}void splay(int x,int g) { down(x); while(pre[x] != g) { if(pre[pre[x]] == g) rotate(x,ch[pre[x]][0] == x); else { int y = pre[x]; int kind = (ch[pre[y]][0] == y); if(ch[y][kind] == x) { rotate(x,!kind) ; rotate(x,kind); } else { rotate(y,kind); rotate(x,kind); } } } up(x); if(g == 0) root = x;}int get_kth(int x,int k) { down(x); int s = size[ch[x][0]]; if(s == k-1) return x; if(s >= k) return get_kth(ch[x][0],k); else return get_kth(ch[x][1],k-s-1);}int get_min(int x) { down(x); while(ch[x][0]) { x = ch[x][0]; down(x); } return x;}int get_max(int x) { down(x); while(ch[x][1]) { x = ch[x][1]; down(x); } return x;}int get_pre(int x) { int now = ch[x][0]; while(ch[now][1]) { now = ch[now][1]; } return now;}int get_suc(int x) { int now = ch[x][1]; while(ch[now][0]) { now = ch[now][0]; } return now;}void rev(int l,int r) { int x = get_kth(root,l); int y = get_kth(root,r+2); splay(x,0); splay(y,root); lazy[ch[ch[root][1]][0]] ^= 1;}void cut(int l,int r,int c) { int x = get_kth(root,l); int y = get_kth(root,r+2); splay(x,0); splay(y,root); int tmp = ch[ch[root][1]][0]; ch[ch[root][1]][0] = 0; up(ch[root][1]); up(root); int z = get_kth(root,c+1); splay(z,0); int m = get_min(ch[root][1]); splay(m,root); ch[ch[root][1]][0] = tmp; pre[ch[ch[root][1]][0]] = ch[root][1]; up(ch[root][1]); up(root);}void print(int x) { if(x == 0) return ; down(x); print(ch[x][0]); if(cnt >= 1 && cnt <= n) { if(cnt > 1) printf(" "); printf("%d",key[x]); } cnt ++; print(ch[x][1]);}char str[11];int a,b,c;int main() { while(scanf("%d%d",&n,&q) != EOF) { if(n == -1 && q == -1) break; init(); while(q--) { scanf("%s",str); if(str[0] == 'C') { scanf("%d%d%d",&a,&b,&c); cut(a,b,c); } if(str[0] == 'F') { scanf("%d%d",&a,&b); rev(a,b); } } cnt = 0; print(root); puts(""); } return 0;}