输出3 1 2 4 3 5

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lid (id << 1)
#define rid (id << 1 | 1)
const int N = 1e5+5;
/*
二叉搜索树，又称二叉搜索树，
是一种优化查询数字的复杂度的
数据结构，他的结点严格满足左

结点小于根节点，右结点大于根节点
son[0]左儿子 son[1]右儿子
val 值
cnt 有多少个这个值
siz 所在子树元素个数
fa 父节点
*/
struct node{
	int son[2];
	int val;
	int cnt;
	int siz;
	int fa;
	int tag;
}tr[2000005];
int root, tot;
int n, m;
int a[N];
bool Dir(int x){
	return tr[tr[x].fa].son[1] == x;
}
void pushup(int x){
	tr[x].siz = tr[tr[x].son[0]].siz + tr[tr[x].son[1]].siz + tr[x].cnt;
}
void pushdown(int x){
	if (x && tr[x].tag){
		tr[tr[x].son[0]].tag ^= 1;
		tr[tr[x].son[1]].tag ^= 1;
		swap(tr[x].son[0], tr[x].son[1]);
		tr[x].tag = 0;
	}
}
void rorate(int x){
	int y = tr[x].fa, z = tr[y].fa, k = Dir(x), w = tr[x].son[k ^ 1];
	pushdown(x), pushdown(y);
	tr[z].son[Dir(y)] = x;tr[x].fa = z;
	tr[x].son[k ^ 1] = y;tr[y].fa = x;
	tr[y].son[k] = w;tr[w].fa = y;
	pushup(x);pushup(y);
}
void splay(int x, int goal = 0){
	while (tr[x].fa != goal){
		int y = tr[x].fa, z = tr[y].fa;
		if (z != goal){
			if (Dir(x) == Dir(y)) rorate(y);
			else rorate(x);
		}
		rorate(x);
	}
	if (!goal) root = x;
}
void find(int x){
	if (!root) return;
	int cur = root;
	while (tr[cur].son[x > tr[cur].val] && tr[cur].val != x){
		pushdown(cur);
		cur = tr[cur].son[x > tr[cur].val];
	}
	splay(cur);
}
void rev(int l, int r){
	int a = l - 1, b = r + 1;
	find(a), a = root;
	find(b), b = root;
	splay(a), splay(b, a);
	int cur = tr[root].son[1];
	cur = tr[cur].son[0];
	tr[cur].tag ^= 1;
}
void print(int x){
	pushdown(x);
	if (tr[x].son[0])print(tr[x].son[0]);
	int tmp = tr[x].val;
	if (tmp >= 1 && tmp <= n) cout << tmp << ' ';
	if (tr[x].son[1]) print(tr[x].son[1]); 
}
void build(int &k, int l, int r, int f){
	if (l > r){
		k = 0;
		return;
	}
	int mid = (l + r) >> 1;
	k = ++tot;
	tr[k].siz = tr[k].cnt = 1;
	tr[k].fa = f;
	tr[k].val = a[mid];
	build(tr[k].son[0], l, mid - 1, k);
	build(tr[k].son[1], mid + 1, r, k);
	pushup(k);
}
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	a[1] = -INT_MAX, a[n + 2] = INT_MAX;
	for (int i = 2;i <= n + 1;i++) a[i] = i - 1;
	build(root, 1, n + 2, 0);
	//print(root);
	while (m--){
		int l, r;
		cin >> l >> r;
		rev(l, r);
	}
	print(root);
	return 0;
}