无旋 Treap 球调

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
struct node {
    node *ch[2];
    int val, rk, cnt, siz, prio;
    node(int v) {
        val = v; cnt = siz = 1;
        ch[0] = ch[1] = nullptr;
        prio = rand();
    }
    bool rev = 0;
    void upd_siz() {
        siz = cnt;
        if(ch[0] != nullptr) siz += ch[0] -> siz;
        if(ch[0] != nullptr) siz += ch[1] -> siz;
    }
    void pushdown() {
        swap(ch[0], ch[1]);
        if(ch[0] != nullptr) ch[0] -> rev ^= 1;
        if(ch[1] != nullptr) ch[1] -> rev ^= 1;
        rev = 0;
    }
    void check() {if(rev) pushdown();}
};
#define gc getchar
#define pc putchar
inline int read() {
    int x = 0; char ch = gc();
    while(ch < '0' || ch > '9') ch = gc();
    while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = gc();
    return x;
}
inline void write(int x) {
    if(x > 9) write(x / 10);
    pc(x % 10 + '0');
}
node *rt;
int siz(node *cur) {
    return cur == nullptr ? 0 : cur -> siz;
}
pair<node*, node*> split(node *cur, int sz) {
    if(cur == nullptr) return {nullptr, nullptr};
    cur -> check();
    if(sz <= siz(cur -> ch[0])) {
        auto tmp = split(cur -> ch[0], sz);
        cur -> ch[0] = tmp.second;
        cur -> upd_siz();
        return {tmp.first, cur};
    }
    else {
        auto tmp = split(cur -> ch[1], sz - siz(cur -> ch[0]) - 1);
        cur -> ch[1] = tmp.first;
        cur -> upd_siz();
        return {cur, tmp.second}; 
    }
}
node *merge(node *a, node *b) {
    if(a == nullptr && b == nullptr) return nullptr;
    if(a != nullptr && b == nullptr) return a;
    if(b != nullptr && a == nullptr) return b;
    a -> check(); b -> check();
    if(a -> prio < b -> prio) {
        a -> ch[1] = merge(a -> ch[1], b);
        a -> upd_siz();
        return a;
    }
    else {
        b -> ch[0] = merge(a, b -> ch[0]);
        b -> upd_siz();
        return b;
    }
}
void ins(int val) {
    auto tmp = split(rt, val);
    auto x = split(tmp.first, val - 1);
    node *new_node;
    if(x.second == nullptr) new_node = new node(val);
    node *y = merge(x.first, x.second == nullptr ? new_node : x.second);
    rt = merge(y, tmp.second);
}
void rev(int l, int r) {
    auto L = split(rt, l - 1);
    auto R = split(L.second, r - l + 1);
    R.first -> rev = 1;
    rt = merge(L.first, merge(R.first, R.second));
}
void print(node *cur) {
    if(cur == nullptr) return ;
    cur -> check();
    print(cur -> ch[0]);
    write(cur -> val); pc(' ');
    print(cur -> ch[1]);
}
int main() {
    srand(time(0));
    int n = read(), m = read();
    for(int i = 1; i <= n; i++) ins(i);
    while(m--) {
        int l = read(), r = read();
        rev(l, r);
    }
    print(rt);
    return 0;
}