具体方法：使用 Treap 建树，将树解剖出所求区域 $[k1-k2]$，将所求区域的根节点打上标记，最后中序遍历输出，若遇到被标记的点，则将标记下传，并交换左右字数

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
const int INF = 0x7fffffff;

struct node {
	int val;
	bool reversed;
	int count;
	int pr;
	int left, right;
}tre[N];

int counter = 0;
int root = -1;

int count(int u){return (u == -1)? 0 : tre[u].count;}

void pushup(int u){
	tre[u].count = count(tre[u].left) + count(tre[u].right) + 1;
}

void pushdown(int u) {
	if(tre[u].reversed){
		if(tre[u].left != -1) tre[tre[u].left].reversed = !tre[tre[u].left].reversed;
		if (tre[u].right != -1) tre[tre[u].right].reversed = !tre[tre[u].right].reversed;
		swap(tre[u].left, tre[u].right);
		tre[u].reversed = false;
	}
}

void replace_by_child(int c,int u,int f) {
	if (f == -1) root = c;
	else if (tre[f].left == u) tre[f].left = c;
	else if (tre[f].right == u) tre[f].right = c;
}

void right_rotate(int u,int f) {
	int c = tre[u].left;
	tre[u].left = tre[c].right;
	tre[c].right = u;
	pushup(u);
	pushup(c);
	replace_by_child(c,u,f);
}

void left_rotate(int u, int f) {
	int c = tre[u].right;
	tre[u].right = tre[c].left;
	tre[c].left = u;
	pushup(u);
	pushup(c);
	replace_by_child(c,u,f);
}

void make_new(int &u,int val,int f,bool is_left){
	u = counter++;
	tre[u].val = val;
	tre[u].reversed = false;
	tre[u].pr = rand();
	tre[u].count = 1;
	tre[u].left = -1;
	tre[u].right = -1;
	if (f == -1) root = u;
	else if (is_left) tre[f].left = u;
	else tre[f].right = u;
}

void insert(int k, int val, int u, int f = -1, bool is_left = true){
	if (u == -1) make_new(u,val,f,is_left);
	
	else if (k <= count(tre[u].left) + 1) {
		pushdown(u);
		insert(k, val, tre[u].left, u, true);
		pushup(u);
		if (tre[tre[u].left].pr > tre[u].pr) right_rotate(u, f);
	}
	else{
		pushdown(u);
		insert(k - count(tre[u].left) - 1, val, tre[u].right, u, false);
		pushup(u);
		if (tre[tre[u].right].pr > tre[u].pr) left_rotate(u, f);
	}
}

pair<int, int> split(int k, int u) {
	if (u == -1) return make_pair(-1, -1);
	else if (k < count(tre[u].left) + 1) {
		pushdown(u);
		pair<int, int> p = split(k, tre[u].left);
		tre[u].left = p.second;
		pushup(u);
		return make_pair(p.first, u);
	}
	else {
		pushdown(u);
		pair<int, int> p = split(k - count(tre[u].left) - 1, tre[u].right);
		tre[u].right = p.first;
		pushup(u);
		return make_pair(u, p.second);
	}
}

void dfs(int u) {
	if(u == -1)	return;
	else{
		pushdown(u);
		dfs(tre[u].left);
		printf("%d ",tre[u].val);
		dfs(tre[u].right);
	}
}

int merge(int u, int v) {
	if (u == -1) return v;
	else if (v == -1) return u;
	else if (tre[u].pr > tre[v].pr) {
		pushdown(u);
		tre[u].right = merge(tre[u].right, v);
		pushup(u);
		return u;
	}
	else{
		pushdown(v);
		tre[v].left = merge(u, tre[v].left);
		pushup(v);
		return v;
	}
}

int m,n;

int main(){
//	freopen("P3391_1.in","r",stdin);
	
	srand(114514);
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++) insert(i,i,root);
	
	//dfs(root);
	//printf("\n");
	
	for (int i=1;i<=m; ++i) {
		int k1, k2;
		scanf("%d%d", &k1, &k2);
		if(k1 > k2) swap(k1,k2);
		
		pair<int,int> p2 = split(k2, root);
		pair<int,int> p1 = split(k1 - 1, p2.first);
		int left = p1.first;
		int right = p2.second;
		int n = p1.second;
		tre[n].reversed = !tre[n].reversed;
		left = merge(left, n);
		root = merge(left, right);
		//dfs(root);
	//	printf("\n");
	}
	dfs(root);
	return 0;
}