HDU – 3487 Play with Chain __ Splay

Play with Chain Splay

 Source

HDU - 3487

My Solution

题意：对1~n这n个数，进行m次操作，分别可以进行区间移动和区间反转，求最终的序列。

Splay

Splay的基础题，按照要求进行区间移动和区间反转即可。

复杂度 O(m*logn)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 3e5 + 8;
int n;
bool flag;

struct SplayTree{
    int ch[MAXN][2], fa[MAXN], tot, root;
    int val[MAXN], reversed[MAXN], sz[MAXN];
    int newnode(int f, int u){
        reversed[tot] = ch[tot][0] = ch[tot][1] = 0;
        fa[tot] = f; val[tot] = u; sz[tot] = 1;
        return tot ++;
    }
    void init(){
        tot = 1; ch[0][0] = ch[0][1] = fa[0] = sz[0] = 0;
    }
    void build(int f, int &x, int l, int r){
        if (l > r) return;
        int mid = (l + r) >> 1;
        x = newnode(f, mid);
        build(x, ch[x][0], l, mid - 1);
        build(x, ch[x][1], mid + 1, r);
        pushup(x);
    }

    void pushdown(int x){
        if(!reversed[x]) return;
        reversed[ch[x][0]] ^= 1;
        reversed[ch[x][1]] ^= 1;
        swap(ch[x][0], ch[x][1]);
        reversed[x] = 0;
    }
    void pushup(int x){
        sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
    }
    void _rotate(int x, int kind){
        int y = fa[x];
        ch[y][!kind] = ch[x][kind];
        fa[ch[x][kind]] = y;
        if(fa[y]) ch[fa[y]][y == ch[fa[y]][1]] = x;
        fa[x] = fa[y]; fa[y] = x;
        ch[x][kind] = y;
        sz[x] = sz[y];
        pushup(y);
    }
    void splay(int x, int r){
        int y, z;
        for (int f = fa[r]; fa[x] != f; ){
            if(fa[fa[x]] == f){_rotate(x, x == ch[fa[x]][0]); return; }
            y = x == ch[fa[x]][0], z = fa[x] == ch[fa[fa[x]]][0];
            y^z ? (_rotate(x, y), _rotate(x, z)) : (_rotate(fa[x], z), _rotate(x, y));
        }
    }
    void _find(int &x, int k){
        for (int i = x, j = k; ; ){
            pushdown(i);
            if(sz[ch[i][0]] == j){splay(i, x); x = i; break; }
            if (sz[ch[i][0]] > j){i = ch[i][0]; continue; }
            j -= sz[ch[i][0]] + 1; i = ch[i][1];
        }
    }
    void _reverse(int&x, int l, int r){
        _find(x, l - 1);
        _find(ch[x][1], r - l + 1);
        reversed[ch[ch[x][1]][0]] ^= 1;
    }
    void cut_insert(int&x, int l, int r, int c){
        _find(x, l - 1);
        _find(ch[x][1], r - l + 1);
        int add = sz[ch[ch[x][1]][0]], temp = ch[ch[x][1]][0];
        sz[x] -= add; sz[ch[x][1]] -= add;
        ch[ch[x][1]][0] = 0;
        _find(x, c);
        _find(ch[x][1], 0);
        ch[ch[x][1]][0] = temp;
        fa[temp] = ch[x][1];
        sz[ch[x][1]] += add;
        sz[x] += add;
    }
    void traversal(int x){
        pushdown(x);
        if(ch[x][0]) traversal(ch[x][0]);
        if(val[x] != 0 && val[x] != n + 1){
            if(flag) cout << " ";
            cout << val[x]; flag = true; } if(ch[x][1]) traversal(ch[x][1]); } }spt; string s; int main() { #ifdef LOCAL freopen("SplayTree.in", "r", stdin); //freopen("SplayTree.out", "w", stdout); #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); int m, l, r, c; while(cin >> n >> m){
        if(n == -1) break;
        spt.init(); spt.root = 0;
        spt.build(0, spt.root, 0, n + 1);
        while(m--){
            cin >> s;
            cin >> l >> r;
            if(s[0] == 'C') cin >> c, spt.cut_insert(spt.root, l, r, c);
            else spt._reverse(spt.root, l, r);
        }
        flag = false;
        spt.traversal(spt.root);
        cout << "n";

    }
    return 0;
}