牛客网暑期ACM多校训练营（第三场）C.Shuffle Cards

题意:

给你一个n，代表序列1,2,3,...n.给你若干个区间si,pi代表L=si,R=si+pi-1,的区间[L,R] 删除并插入到序列的开头。

样例

5 3
2 3

初始序列[1 2 3 4 5], 操作区间[2, 4]吧 把元素{2,3,4}丢到开头{2,3,4,1,5}。

分析

题意很简单，对区间一段序列移动到另一位置。
1，数组删除，涉及大量元素移动操作。
2，链表模拟，找到区间L,R的端点需要线性扫描。
组合一下【块状链表】，复杂度O(n*sqrt(n))不知道能不能过。

比赛的时候想起的是splay的能在log(n)的时间内删除一个区间，在log(n)的时间内插入一个区间。复杂度是O(q*log(n))的，然后百度翻个splay板子，splay区间平移，然后改改就1A过了。比赛的改板子过了就没管了，赛后才找到自己的splay在哪里冏

还有一种rope，属于一种非标准的stl函数，也就是不是所有OJ都支持，起码C++11

rope你把他当成vector用，复杂度底层非常优秀，块状链表，平衡树的实习。。。具体我也不懂。

知道名字后你们应该都会去搜索这东西怎么用了，就不多说，用法看函数名都很好懂。

然后在啰嗦一句crope a相当于 rope<char> a。补题的时候现学现卖，这个学一学以后能当***树用

#include <bits/stdc++.h>
#include <ext/rope> //头文件

using namespace std;
using namespace __gnu_cxx; //必备命名空间
const int MAXN = 1e5 + 10;

int n, m;

int main()
{
    while(~scanf("%d %d", &n, &m)) {
        rope<int> rop;
        for(int i = 1; i <= n; i++ ) {
            rop.push_back(i);
        }
        for(int i = 1; i <= m; i++ ) {
            int l, r;
            scanf("%d %d", &l, &r);
//            r = l + r - 1;
            rop.insert(0, rop.substr(l - 1, r));
            rop.erase(l + r - 1, r);
        }
        for(int i = 0; i < n; i++ ) {
            if(i != 0) {
                printf(" ");
            }
            printf("%d", rop[i]);
        }
        puts("");
    }

    return 0;
}

赛后猜正紧补题，然后才是自己的splay板子。splay的区间翻转操作是常规操作，这里不赘述。我们可以通过三次区间翻转来实习一个区间的平移。
1，2，3，4，5 翻转1~4(这里指的是下标)
4，3，2，1，5 翻转1~3
2，3，4，1，5 翻转4~4

或者你写删除一个区间，插入一个区间来实习也可以。基本是个模板题，但是就是这个模板比较高级。没点过splay技能的几乎想不到。第一次在牛客写题解，有错误欢迎指正

然后留下自己又丑又长的splay模板。

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int maxn = 5e5 + 7;
const int inf = 1e9 + 7;

int n, m, arr[maxn];

struct Splay_Tree {

    struct Node {
        int father, childs[2], key, cnt, _size, rev;
        inline void init() {
            father = childs[0] = childs[1] = key = cnt = _size = rev = 0;
        }
        inline void init(int father, int lchild, int rchild, int key, int cnt, int sz) {
            this -> father = father, childs[0] = lchild, childs[1] = rchild;
            this -> key = key, this -> cnt = cnt, _size = sz;
            this -> rev = 0;
        }
    } tre[maxn];
    int sign, root;

    inline void init() {
        sign = root = 0;
    }

    inline bool judge(int x) {
        return tre[ tre[x].father ].childs[1] == x;
    }

    inline void update(int x) {
        if(x) {
            tre[x]._size = tre[x].cnt;
            if(tre[x].childs[0]) {
                tre[x]._size += tre[ tre[x].childs[0] ]._size;
            }
            if(tre[x].childs[1]) {
                tre[x]._size += tre[ tre[x].childs[1] ]._size;
            }
        }
    }

    inline void rotate(int x) {

        int y = tre[x].father, z = tre[y].father, k = judge(x);
        pushdown(y), pushdown(x);
        //tre[y].childs[k] = tre[x].childs[!k], tre[ tre[x].childs[!k] ].father = y;
        //tre[x].childs[!k] = y, tre[y].father = x;
        //tre[z].childs[ tre[z].childs[1] == y ] = x, tre[x].father = z;
        if(k == 0) {///zig
            tre[y].childs[0] = tre[x].childs[1], tre[ tre[x].childs[1] ].father = y;
            tre[x].childs[1] = y, tre[y].father = x;
        } else {    ///zag
            tre[y].childs[1] = tre[x].childs[0], tre[ tre[x].childs[0] ].father = y;
            tre[x].childs[0] = y, tre[y].father = x;
        }
        tre[z].childs[ tre[z].childs[1] == y ] = x, tre[x].father = z;

        update(y);

    }

    inline void splay(int x,int goal) {
        for(int father; (father = tre[x].father) != goal; rotate(x) ) {
            if(tre[father].father != goal) {
                rotate(judge(x) == judge(father) ? father : x);
            }
        }
        if(goal == 0) {
            root = x;
        }
    }

    inline void pushdown(int x) {
        if(x && tre[x].rev) {
            tre[ tre[x].childs[0] ].rev ^= 1;
            tre[ tre[x].childs[1] ].rev ^= 1;
            swap(tre[x].childs[0], tre[x].childs[1]);
            tre[x].rev = 0;
        }
    }

    int build(int l, int r, int fa) {
        if(l > r) {
            return 0;
        }
        int mid = (l + r) >> 1;
        int now = ++ sign;
        tre[now].init(fa, 0, 0, arr[mid], 1, 1);
        tre[now].childs[0] = build(l, mid - 1, now);
        tre[now].childs[1] = build(mid + 1, r, now);
        update(now);
        return now;
    }

    int find(int x) {
        int now = root;
        while(1) {
            pushdown(now);
            if(x <= tre[ tre[now].childs[0] ]._size) {
                now = tre[now].childs[0];
            } else {
                x -= tre[ tre[now].childs[0] ]._size + 1;
                if(!x) {
                    return now;
                }
                now = tre[now].childs[1];
            }
        }
    }

    void reverse(int x, int y) {
        int L = x - 1, R = y + 1, pos;
        L = find(L), R = find(R);
        splay(L, 0);
        splay(R, L);
        pos = tre[root].childs[1];
        pos = tre[pos].childs[0];
        tre[pos].rev ^= 1;
    }

    inline void dfs(int now) {
        pushdown(now);
        if(tre[now].childs[0]) {
            dfs(tre[now].childs[0]);
        }
        if(tre[now].key != -inf && tre[now].key != inf) {
            printf("%d ", tre[now].key);
        }
        if(tre[now].childs[1]) {
            dfs(tre[now].childs[1]);
        }
    }

    void solve(int l, int r) {
        reverse(2, r);
        reverse(2, 2 + r - l);
        reverse(2 + r - l + 1, r);
    }

} S;

int main() {
    scanf("%d %d", &n, &m);
    S.init();
    arr[1] = -inf, arr[n + 2] = inf;
    for(int i = 1; i <= n; i ++ ) {
        arr[i + 1] = i;
    }
    S.root = S.build(1, n + 2, 0);
    for(int i = 1; i <= m; i ++ ) {
        int x, y;
        scanf("%d %d", &x, &y);
        int l = x, r = x + y - 1;
        l++, r++;
        S.solve(l, r);
    }
    S.dfs(S.root);
    return 0;
}