【HDU 3487】Play with Chain Splay

题意

给定$n$个数序列，每次两个操作，将区间$[L,R]$拼接到去掉区间后的第$c$个数后，或者翻转$[L,R]$

Splay区间操作模板，对于区间提取操作，将$L-1$ Splay到根，再将$R+1$ Splay到根节点的右儿子，那么根节点右儿子的左儿子就对应区间$[L,R]$，对于反转操作，通过懒操作下放

代码

#include <bits/stdc++.h>

#define inf 0x7f7f7f7f

using namespace std;

const int N = 500005;

int ch[N][2], fa[N], key[N], lazy[N], sz[N];

int root, tot;

inline int get(int x) {return ch[fa[x]][1] == x;} // left is 0, right is 1

inline void pushup(int x) {

    sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;

}

inline void pushdown(int x) {

    if(lazy[x]) {

        lazy[x] = 0;

        swap(ch[x][0], ch[x][1]);

        lazy[ch[x][0]] ^= 1; lazy[ch[x][1]] ^= 1;

    }

}

inline void rotate(int x) {

    int f = fa[x], ff = fa[f], which = get(x);

    pushdown(f); pushdown(x);

    ch[f][which] = ch[x][which ^ 1];

    fa[ch[f][which]] = f;

    ch[x][which ^ 1] = f;

    fa[f] = x; fa[x] = ff;

    if(ff) ch[ff][ch[ff][1] == f] = x;

    pushup(f); pushup(x);

}

inline void splay(int x, int target) {

    while(fa[x] != target) {

        if(fa[fa[x]] != target) {

            rotate((get(x) == get(fa[x])) ? fa[x] : x);

        }

        rotate(x);

    }

    if(!target) root = x;

}

inline int get_kth(int x, int k) {

    if(!x) return 0;

    while(1) {

        pushdown(x);

        if(k == sz[ch[x][0]] + 1) break;

        if(k > sz[ch[x][0]] + 1) {

            k -= sz[ch[x][0]] + 1; x = ch[x][1];

        }else x = ch[x][0];

    }

    return x;

}

inline int newnode(int v, int f) {

    int x = ++tot;

    ch[x][0] = ch[x][1] = 0; fa[x] = f;

    key[x] = v; sz[x] = 1; lazy[x] = 0;

    return x;

}

int build(int l, int r, int f) {

    if(l > r) return 0;

    int mid = (l + r) / 2;

    int x = newnode(mid, f);

    ch[x][0] = build(l, mid - 1, x);

    ch[x][1] = build(mid + 1, r, x);

    pushup(x);

    return x;

}

inline void init(int x) {root = tot = 0; root = build(0, x + 1, 0);}

inline void cut(int l, int r, int c) {

    splay(get_kth(root, l), 0); splay(get_kth(root, r + 2), root);

    int tmp = ch[ch[root][1]][0];

    ch[ch[root][1]][0] = 0;

    pushup(ch[root][1]); pushup(root);

    splay(get_kth(root, c + 1), 0); splay(get_kth(root, c + 2), root);

    fa[tmp] = ch[root][1];

    ch[ch[root][1]][0] = tmp;

    pushup(ch[root][1]); pushup(root);

}

inline void filp(int l, int r) {

    splay(get_kth(root, l), 0); splay(get_kth(root, r + 2), root);

    lazy[ch[ch[root][1]][0]] ^= 1;

    pushup(ch[root][1]); pushup(root);

}

int n, m, a, b, c;

int cnt;

void out(int x){

    if (!x) return;

    pushdown(x);

    out(ch[x][0]);

    if (key[x] >= 1 && key[x] <= n) {

        cnt++;

        printf("%d", key[x]);

        if (cnt < n) printf(" ");

        else puts("");

    }

    out(ch[x][1]);

}

char opt[20];

int main() {

    while(scanf("%d%d", &n, &m) != EOF) {

        if(n == -1 && m == -1) break;

        init(n);

        for(int i = 1; i <= m ;++i) {

            scanf("%s", opt);

            if(opt[0] == 'C') {

                scanf("%d%d%d", &a, &b, &c); cut(a, b, c);

            }else scanf("%d%d", &a, &b, &c), filp(a, b);

        }

        cnt = 0; out(root);

    }

    return 0;

}

巴特西

【HDU 3487】Play with Chain Splay

题意

代码

最新文章

热门文章