hdu 3487 Play with Chain (Splay树) 区间切割 插入 翻转(二)
--i) #define REP(i, N) for(int i = 0; i < (N); ++i) #define CLR(A,value) memset(A,value,sizeof(A)) //INPUT #define RI(n) scanf("%d", &n) #define RII(n, m) scanf("%d%d", &n, &m) #define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k) typedef long long LL; typedef vector
VI; const int INF = 0x3f3f3f3f; const double eps = 1e-10; const int maxn = 311111; #define ll ch[x][0] #define rr ch[x][1] #define KT (ch[ch[root][1]][0]) vector
ans; struct SplayTree{ int ch[maxn][2]; int pre[maxn], sz[maxn]; int val[maxn], flip[maxn]; int root, tot; void Rotate(int x, int f) { int y = pre[x]; down(y); down(x);/// ch[y][!f] = ch[x][f]; pre[ch[x][f]] = y; pre[x] = pre[y]; if (pre[x]) ch[pre[y]][ch[pre[y]][1] == y] = x; ch[x][f] = y; pre[y] = x; up(y);/// } void Splay(int x, int goal) { down(x);/// while (pre[x] != goal) { down(pre[pre[x]]); down(pre[x]); down(x); /// 翻转操作down!!! if (pre[pre[x]] == goal) Rotate(x, ch[pre[x]][0] == x); else { int y = pre[x], z = pre[y]; int f = ( ch[z][0] == y ); if (ch[y][f] == x) Rotate(x, !f), Rotate(x, f); else Rotate(y, f), Rotate(x, f); } } up(x);/// if (goal == 0) root = x; } void RTO(int k, int goal) { int x = root; down(x);///!!!flip while (sz[ll] + 1 != k) { if (k < sz[ll] + 1) x = ll; else { k -= (sz[ll] + 1); x = rr; } down(x); } Splay(x, goal); } void up(int x) { sz[x] = 1 + sz[ll] + sz[rr]; } void Reverse(int x)/// { // if (!x) return ;// swap(ll, rr);///!!! flip[x] ^= 1; } void down(int x) { if (flip[x]) { Reverse(ll); Reverse(rr); flip[x] = 0; } } void Newnode(int &x, int c, int f)///& { x = ++tot; ll = rr = 0; pre[x] = f; sz[x] = 1; flip[x] = 0; val[x] = c; } void Build(int &x, int l, int r, int f)///& { if (l >
r) return ; int m = (l + r) >> 1; Newnode(x, m, f); Build(ll, l, m - 1, x); Build(rr, m + 1, r, x); up(x); } void Init(int n) { ch[0][0] = ch[0][1] = pre[0] = sz[0] = 0; val[0] = 0; flip[0] = 0; root = tot = 0; Newnode(root, -1, 0); Newnode(ch[root][1], -1, root); Build(KT, 1, n, ch[root][1]);/// up(ch[root][1]); up(root);/// } /// void CUT() { int x, y, z; scanf("%d%d%d",&x, &y, &z); int tmp; RTO(x, 0); RTO(y + 2, root); tmp = KT; KT = 0; up(ch[root][1]); up(root);///up RTO(z + 1, 0); RTO(z + 2, root); KT = tmp; pre[tmp] = ch[root][1];///!!!修改pre up(ch[root][1]); up(root);///up } void FLIP() { int x, y; scanf("%d%d", &x, &y); RTO(x, 0); RTO(y + 2, root); Reverse(KT); } void out(int x) { if (!x) return ; down(x);///!!! out(ll); if (val[x] > 0) ans.push_back(val[x]); out(rr); } }sp; int main () { int n, m; char op[5]; ans.clear(); int nn; while (~scanf("%d%d", &n, &m)) { if (n == -1 && m == -1) break; sp.Init(n); for (int i = 1; i <= m; i++) { scanf("%s", op); if (op[0] == 'C') sp.CUT(); else sp.FLIP(); } sp.out(sp.root); nn = ans.size(); REP(i, nn) { if(i) printf(" "); printf("%d", ans[i]); } printf("\n"); ans.clear(); } return 0; }