洛谷【P3391】文艺平衡树(fhq Treap区间操作)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
struct node{
    int l, r, val, key, size;
    bool reverse;
}tree[maxn];
std::mt19937 rnd(233);
int n, m, tot, root;

inline int read(){
    int s = 0, w = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

inline void print(int x){
    if(x < 0) x = ~x + 1, putchar('-');
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

inline int newnode(int val){
    tree[++tot].val = val;
    tree[tot].key = rnd();
    tree[tot].size = 1;
    return tot;
}

inline void update(int now){
    tree[now].size = tree[tree[now].l].size + tree[tree[now].r].size + 1;
}

inline void pushdown(int now){
    swap(tree[now].l, tree[now].r);
    tree[tree[now].l].reverse ^= 1;
    tree[tree[now].r].reverse ^= 1;
    tree[now].reverse = false;
}

void split(int now, int siz, int &x, int &y){
    if(!now) x = y = 0;
    else{
        if(tree[now].reverse) pushdown(now);
        if(tree[tree[now].l].size < siz)
            x=now, split(tree[now].r, siz-tree[tree[now].l].size - 1, tree[now].r, y);
        else
            y=now, split(tree[now].l, siz, x, tree[now].l);
        update(now);
    }
}

int merge(int x, int y){
    if(!x || !y) return x + y;
    if(tree[x].key < tree[y].key){
        if(tree[x].reverse) pushdown(x);
        tree[x].r = merge(tree[x].r, y);
        update(x);
        return x;
    }
    else{
        if(tree[y].reverse) pushdown(y);
        tree[y].l = merge(x, tree[y].l);
        update(y);
        return y;
    }
}

void reverse(int l, int r){
    int x, y, z;
    split(root, l - 1, x, y);
    split(y, r - l + 1, y, z);
    tree[y].reverse ^= 1;
    root = merge(merge(x, y), z);
}

void ldr(int now){
    if(!now) return;
    if(tree[now].reverse) pushdown(now);
    ldr(tree[now].l);
    print(tree[now].val);
    putchar(' ');
    ldr(tree[now].r);
}

int main(int argc, char const *argv[])
{
    n = read(), m = read();
    for(int i = 1; i <= n; i++)
        root = merge(root, newnode(i));
    while(m--){
        int l, r;
        l = read(), r = read();
        reverse(l, r);
    }
    ldr(root);
}
/*
* ┌───┐   ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐
* │Esc│   │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S L│P/B│  ┌┐    ┌┐    ┌┐
* └───┘   └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘  └┘    └┘    └┘
* ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
* │~ `│! 1│@ 2│# 3│$ 4│% 5│^ 6│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │Num│ / │ * │ - │
* ├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤
* │ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ | \ │ │Del│End│PDn│ │ 7 │ 8 │ 9 │   │
* ├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │
* │ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│" '│ Enter  │               │ 4 │ 5 │ 6 │   │
* ├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤     ┌───┐     ├───┼───┼───┼───┤
* │ Shift  │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│  Shift   │     │ ↑ │     │ 1 │ 2 │ 3 │   │
* ├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││
* │ Ctrl│ Win│ Alt│         Space         │ Alt│ Win│Menu│Ctrl│ │ ← │ ↓ │ → │ │   0   │ . │←─┘│
* └─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘
*/