FHQ-Treap 0pts 求助

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
mt19937 myrand(time(0));
int n, m, root = 0;
struct node {
	int val;
	unsigned pri;
	int cnt, size;
	int lc, rc;
	bool flag;
} nd[MAXN];
int num_node;
int New(int val) {
	num_node++;
	nd[num_node].val = val;
	nd[num_node].pri = myrand();
	nd[num_node].cnt = nd[num_node].size = 1;
	nd[num_node].lc = nd[num_node].rc = 0;
	nd[num_node].flag = false;
	return num_node;
}
void Update(int x) {
	nd[x].size = nd[nd[x].lc].size + nd[x].cnt + nd[nd[x].rc].size;
}
void Down(int x) {
	if (!nd[x].flag)return;
	swap(nd[x].lc, nd[x].rc);
	nd[nd[x].lc].flag = !nd[nd[x].lc].flag;
	nd[nd[x].rc].flag = !nd[nd[x].rc].flag;
	nd[x].flag = false;
}
void split_val(int rt, int k, int &x, int &y) {
	if (rt == 0) {
		x = y = 0;
		return;
	}
	Down(rt);
	if (nd[rt].val <= k) {
		x = rt;
		split_val(nd[rt].rc, k, nd[rt].rc, y);
	} else {
		y = rt;
		split_val(nd[rt].lc, k, x, nd[rt].lc);
	}
	Update(rt);
}
int merge(int x, int y) {
	if (!x)return y;
	if (!y)return x;
	Down(x);
	Down(y);
	if (nd[x].pri > nd[y].pri) {
		nd[x].rc = merge(nd[x].rc, y);
		Update(x);
		return x;
	} else {
		nd[y].lc = merge(x, nd[y].lc);
		Update(y);
		return y;
	}
}
void split_rk(int rt, int rk, int &x, int &y) {
	if (rt == 0) {
		x = y = 0;
		return;
	}
	Down(rt);
	if (nd[nd[rt].lc].size + nd[rt].cnt >= rk) {
		y = rt;
		split_rk(nd[rt].lc, rk, x, nd[rt].lc);
	} else {
		x = rt;
		split_rk(nd[rt].rc, rk - nd[nd[rt].lc].size - nd[rt].cnt, nd[rt].rc, y);
	}
	Update(rt);
}
void insert(int val) {
	int a = 0, b = 0, c = 0;
	split_val(root, val, a, c);
	split_val(a, val - 1, a, b);
	if (b) {
		nd[b].cnt++;
		Update(b);
	} else {
		b = New(val);
	}
	root = merge(merge(a, b), c);
}
void Rotate(int l, int r) {
	int a, b, c;
	split_rk(root, r, b, c);
	split_rk(b, l - 1, a, b);
	nd[b].flag = !nd[b].flag;
	root = merge(merge(a, b), c);
}
void getans(int rt) {
	if (rt == 0)return;
	Down(rt);
	getans(nd[rt].lc);
	if (rt > 0)cout << rt - 0 << " ";
	getans(nd[rt].rc);
}
int main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m; 
	for (int i = 1; i <= n; i++) {
		insert(i);
	}
	for (int i = 1; i <= m; i++) {
		int l, r;
		cin >> l >> r;
		Rotate(l, r);
	}
	getans(root);
	return 0;
}