FHQTreap求调

#include <bits/stdc++.h>
using namespace std;

mt19937 mt(time(nullptr));
uniform_int_distribution<>dis(INT_MIN, INT_MAX);

struct node {
    int val, pri, lson, rson, size;
    bool lazy;//那一天 人类终于回想起了 被线段树所支配的恐惧
} t[100010];

int cur;

void newnode (int val) {
    ++cur;
    t[cur].val = val;
    t[cur].pri = dis(mt);
    t[cur].lson = t[cur].lazy = t[cur].rson = 0;
    t[cur].size = 1;
}

void pushup (int root) {
    t[root].size = t[t[root].lson].size + t[t[root].rson].size + 1;
}

void pushdown (int root) {
    swap(t[root].lson, t[root].rson);
    t[t[root].lson].lazy ^= 1;
    t[t[root].rson].lazy ^= 1;
    t[root].lazy = 0;
}

void split (int root, int siz, int &l, int &r) {
    if (root == 0) {
        l = r = 0;
        return;
    }
    if (t[root].lazy)
        pushdown(root);
    if (t[t[root].lson].size - 1 <= siz) {
        l = root;
        split(t[root].rson, siz - t[t[root].lson].size - 1, t[root].rson, r);
    } else {
        r = root;
        split(t[root].lson, siz, l, t[root].lson);
    }
    pushup(root);
}

int merge (int x, int y) {
    if (x == 0 || y == 0)
        return x + y;
    if (t[x].pri < t[y].pri) {
        if (t[x].lazy)
            pushdown(x);
        t[x].rson = merge(t[x].rson, y);
        pushup(x);
        return x;
    } else {
        if (t[y].lazy)
            pushdown(y);
        t[y].lson = merge(x, t[y].lson);
        pushup(y);
        return y;
    }
}

void inorder (int root) {
    if (t[root].lazy)
        pushdown(root);
    if (t[root].lson)
        inorder(t[root].lson);
    cout << t[root].val << " ";
    if (t[root].rson)
        inorder(t[root].rson);
}

int n, m, x, y, l, r, p, root = 1;

int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        newnode(i);
        root = merge(root, i);
    }
    while (m--) {
        cin >> x >> y;
        split(root, y, l, r);
        split(l, x - 1, l, p);
        t[p].lazy ^= 1;
        root = merge(merge(l, p), r);
    }
    inorder (root);
    return 0;
}