1. fhq-treap实现
#include <bits/stdc++.h>
//平衡树的区间修改
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define pre(i, a, b) for(int i = (a); i >= (b); i--)
#define Ede(i, u) for(int i = h[u]; i; i = ne[i])
#define go(i, a) for(auto i : a)
//#define int long long
#define uint unsigned int
#define LL long long
#define ULL unsigned long long
#define PII pair<int, int>
#define PIL pair<int, long long>
#define PLI pair<long long, int>
#define PLL pair<long long, long long>
#define mp make_pair
#define eb emplace_back
#define opb pop_back
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define sf scanf
#define prf printf
#define el putchar('\n')
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define mmc(arr1, arr2) memcpy(arr1, arr2, sizeof(arr2))
#define Db(x) prf("test(%s): ", x)
const int inf = 0x3f3f3f3f;
template <typename T> inline void rd(T &x){
x = 0; bool f = true; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') f = false; ch = getchar();}
while(ch >= '0' && ch <= '9'){ x = (x << 1) + (x << 3) + (ch ^ '0'); ch = getchar();}
if(!f) x = -x;
}
template <typename T, typename ...Args> inline void rd(T &x, Args &...args){ rd(x); rd(args...);}
#define ls(p) fhq[p].l
#define rs(p) fhq[p].r
#define val(p) fhq[p].val
#define key(p) fhq[p].key
#define siz(p) fhq[p].siz
#define tag(p) fhq[p].tag
using namespace std;
const int N = 1e5 + 10;
int n, m;
struct Node{
int l, r;
int val;
uint key;
int siz;
int tag;
Node(){ tag = 0;}
}fhq[N];
int root, cnt;
mt19937 ran(time(0));
int newnode(int val){
++cnt;
val(cnt) = val;
key(cnt) = ran();
siz(cnt) = 1;
return cnt;
}
void pushup(int p){
siz(p) = siz(ls(p)) + siz(rs(p)) + 1;
}
void pushdown(int p){
if(!tag(p)) return;
swap(ls(p), rs(p));
//addtag
tag(ls(p)) ^= 1;
tag(rs(p)) ^= 1;
tag(p) = 0;
}
void split(int p, int siz, int &x, int &y){
if(!p){ x = y = 0; return;}
pushdown(p);
if(siz(ls(p)) < siz){
x = p;
split(rs(p), siz - (siz(ls(p)) + 1), rs(x), y);
}else{
y = p;
split(ls(p), siz, x, ls(y));
}
pushup(p);
}
int merge(int x, int y){
if(!x || !y) return x + y;
if(key(x) > key(y)){
pushdown(x);
rs(x) = merge(rs(x), y);
pushup(x);
return x;
}else{
pushdown(y);
ls(y) = merge(x, ls(y));
pushup(y);
return y;
}
}
void reverse(int l, int r){
int x, y, z;
split(root, r, x, z);
split(x, l - 1, x, y);
tag(y) ^= 1;
root = merge(merge(x, y), z);
}
void morder(int p){
if(!p) return;
pushdown(p);
morder(ls(p));
prf("%d ", val(p));
morder(rs(p));
}
int main(){
/*
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
*/
rd(n, m);
rep(i, 1, n) root = merge(root, newnode(i));
rep(i, 1, m){
int l, r; rd(l, r);
reverse(l, r);
}
morder(root);
return 0;
}