题解 | 区间翻转

struct Nd {
    int val, pri, sz;
    bool rev;
    Nd *l, * r;
    Nd(int _v = 0, int _p = 0): val(_v), pri(_p), sz(1), rev(0), l(0), r(0) {}
};

int getsz(Nd* t) {
        return t ? t->sz : 0;
    }
    void pull(Nd* t) {
        if (!t) return;
        t->sz = 1 + getsz(t->l) + getsz(t->r);
    }
    void rev(Nd* t) {
        if (!t) return;
        t->rev ^= 1;
        swap(t->l, t->r);
    }
    void push(Nd* t) {
        if (!t or !t->rev) return;
        if (t->l) rev(t->l);
        if (t->r) rev(t->r);
        t->rev = 0;
    }
    void split(Nd* t, int k, Nd* &l, Nd* &r){
        if(!t){ l = r = nullptr; return; }
        push(t);
        if(getsz(t->l) >= k){
            split(t->l, k, l, t->l);
            r = t;
            pull(r);
        } else {
            split(t->r, k - getsz(t->l) - 1, t->r, r);
            l = t;
            pull(l);
        }
    }
    Nd* merge(Nd* a, Nd* b){
        if(!a) return b;
        if(!b) return a;
        if(a->pri > b->pri){
            push(a);
            a->r = merge(a->r, b);
            pull(a);
            return a;
        } else {
            push(b);
            b->l = merge(a, b->l);
            pull(b);
            return b;
        }
    }

    void inord(Nd* t, vector<int>& out){
        if(!t) return;
        push(t);
        if(t->l) inord(t->l, out);
        out.push_back(t->val);
        if(t->r) inord(t->r, out);
    }

void solve() {
    int n, k; 
    rd(n, k);
    mt19937 rng((unsigned)chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> uid(INT_MIN, INT_MAX);
    Nd* rt = 0;
    rep(i, 1, n) {
        Nd* nd = new Nd(i, uid(rng));
        rt = merge(rt, nd);
    }
    rep(i, 0, k - 1) {
        int l, r; rd(l, r);
        Nd *a, *b, *c;
        split(rt, l - 1, a, b);
        split(b, r - l + 1, b, c);
        if (b) rev(b);
        rt = merge(merge(a, b), c);
    }
    vector<int> ans;
    inord(rt, ans);
    println(ans);
}