MnZn刚学fhqTreap，样例过了全WA，求调

rt

using namespace std;
typedef long long int ll;
const int N = 2e6 + 10;
struct node {
    int l, r, siz;
    ll key; bool tage;
    node() { l = r = key = siz = tage = 0; }
}fhq[N];
inline void upd(int x) { fhq[x].siz = fhq[fhq[x].l].siz + fhq[fhq[x].r].siz + 1; }
int cnt = 0, rt = 0; mt19937 rd;
inline int newnode(ll val) {
    fhq[++cnt].key = rd();
    fhq[cnt].siz = 1;
    return cnt;
}
inline void pushdw(int x) {
    if (fhq[x].tage) {
        swap(fhq[x].l, fhq[x].r);
        if(fhq[x].l)fhq[fhq[x].l].tage ^= 1;
        if(fhq[x].r)fhq[fhq[x].r].tage ^= 1;
        fhq[x].tage = 0;
    }
}
void split(int v, int siz, int& x, int& y) {
    if (!v) { x = y = 0; return; }
    if (fhq[v].siz <= siz) {
        x = v;
        split(fhq[v].r, siz - fhq[fhq[x].l].siz - 1, fhq[v].r, y);
    }
    else {
        y = v;
        split(fhq[v].l, siz, x, fhq[v].l);
    }
    upd(v);
}
int merge(int x, int y) {
    if (!x || !y)return x + y;
    if (fhq[x].key <= fhq[y].key) {
        if (fhq[x].tage)pushdw(x);
        fhq[x].r = merge(fhq[x].r, y);
        upd(x); return x;
    }
    else {
        if (fhq[y].tage)pushdw(y);
        fhq[y].l = merge(x, fhq[y].l);
        upd(y); return y;
    }
}
int x, y, z, ans;
inline void ins(ll val) {
    x = y = 0; split(rt, val, x, y);
    rt = merge(merge(x, newnode(val)), y);
}
void print(int x) {
    if (x == 0)return;
    pushdw(x);
    print(fhq[x].l);
    cout << x << " ";
    print(fhq[x].r);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(); cout.tie();
    srand((unsigned)time(NULL));
    int n, m, a, b;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)ins(i);
    while (m--) {
        cin >> a >> b;
        x = 0, y = 0, z = 0;
        split(rt, a - 1, x, y);
        split(y, b - a + 1, y, z);
        fhq[y].tage ^= 1; pushdw(y);
        rt = merge(x, merge(y, z));
    }
    print(rt);
    return 0;
}