FHQ树，MLE

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll read() {
	ll X = 0,r = 1;
	char ch = getchar();
	while(!isdigit(ch) && ch != '-') ch = getchar();
	if(ch == '-') r = -1,ch = getchar();
	while(isdigit(ch)) {
		X = X*10+ch-'0';
		ch = getchar();
	}
	return X*r;
}
const int N = 1e5+10;
int n,m,cnt,root;
struct FHQ_Tree{
	int ls,rs;
	int num,pri,siz;
	bool tag;
}c[N];
void newNode(int x){
	cnt++;
	c[cnt].ls = c[cnt].rs = 0;
	c[cnt].siz = 1;
	c[cnt].num = x;
	c[cnt].pri = rand();
}
void update(int x){
	c[x].siz = c[c[x].ls].siz+c[c[x].rs].siz+1;
}
void push_down(int x){
	if(c[x].tag){
		swap(c[x].ls,c[x].rs);
		c[c[x].ls].tag ^= 1;
		c[c[x].rs].tag ^= 1;
		c[x].tag = 0;
	}
}
void split(int x,int k,int &L,int &R){
	if(!x){L = R = 0; return;}
	push_down(x);
	if(c[c[x].ls].siz+1 <= k){
		L = x;
		split(c[x].rs,k-c[c[x].ls].siz-1,c[x].rs,R);
	}else{
		R = x;
		split(c[x].ls,k,L,c[x].ls);
	}
	update(x);
}
int merge(int L,int R){
	if(!L || !R) return L+R;
	if(c[L].pri > c[R].pri){
		push_down(L);
		c[L].rs = merge(c[L].rs,R);
		update(L);
		return L;
	}else{
		push_down(R);
		c[R].ls = merge(L,c[R].ls);
		update(R);
		return R;
	}
}
void inorder(int x){
	if(!x) return;
	push_down(x);
	inorder(c[x].ls);
	cout << c[x].num << " ";
	inorder(c[x].rs);
}
int main() {
	srand(time(0));
	n = read(); m = read();
	for(int i=1;i<=n;i++){
		newNode(i);
		root = merge(root,cnt);
	}
	int x,y,L,R,p;
	while(m--){
		x = read(),y = read();
		L = R = p = 0;
		split(root,y,L,R);
		split(root,x-1,L,p);
		c[p].tag ^= 1;
		root = merge(merge(L,p),R);
	}
	inorder(root);
	return 0;
}