Keyzee @ 2022-07-22 17:03:30
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;
const int MAXN = 100005;
const int MOD = 2147483647;
struct Node
{
int left; //左子树
int right; //右子树
int size; //大小
int val; //值
int key; //平衡种子
int lazy;
}tree[MAXN];
int root, tot;
int add(int val) {
tot++;
tree[tot].size = 1;
tree[tot].val = val;
tree[tot].key = rand() % MOD;
tree[tot].left = 0;
tree[tot].right = 0;
return tot;
}
void update_root(int now) {
int left, right;
left = tree[now].left;
right = tree[now].right;
tree[now].size = tree[left].size + tree[right].size + 1;
}
void pushdown(int x) {
if (tree[x].lazy) {
tree[tree[x].left].lazy ^= 1;
tree[tree[x].right].lazy ^= 1;
swap(tree[x].left, tree[x].right);
tree[x].lazy ^= 1;
}
}
//拆分(now原treap,a左子树,b右子树,val值)
void split_val (int now, int& a, int& b, int val) {
if (now == 0) {
a = 0;
b = 0;
return;
}
if (tree[now].val <= val) {//now左子树中的所有值都小于now,
a = now;
split_val(tree[now].right, tree[a].right, b, val);
}
else {
b = now;
split_val(tree[now].left, a, tree[b].left, val);
}
update_root(now);
}
void split_k(int now, int& a, int& b, int k) {
if (now == 0) {
a = 0;
b = 0;
return;
}
pushdown(now);
if (tree[tree[now].left].size < k) {
a = now;
split_k(tree[now].right, tree[a].right, b, k - tree[tree[now].left].size - 1);
}
else {
b = now;
split_k(tree[now].left, a, tree[b].left, k);
}
update_root(now);
}
void merge_new(int& now, int a, int b) {
if (a == 0 || b == 0) {
now = a + b;
return;
}
pushdown(a), pushdown(b);
//按照key值合并(堆性质)
if (tree[a].key < tree[b].key) {
/**
* a树key值小于b树,那么b树属于a树的后代,因为b树恒大于a树,那么b树一定属于a树的右后代,
* a的左子树不变,直接赋给now,递归合并a的右子树和b
*/
now = a;
merge_new(tree[now].right, tree[a].right, b);
}
else {
now = b;
merge_new(tree[now].left, a, tree[b].left);
}
update_root(now);
}
void find_new(int now, int rank) {//找第k大
while (tree[tree[now].left].size + 1 != rank) {
if (tree[tree[now].left].size >= rank) {
now = tree[now].left;
}
else {
rank -= tree[tree[now].left].size + 1;
now = tree[now].right;
}
}
cout << tree[now].val << "\n";
}
void insert_new(int val) {
int x, y, z;
x = 0;
y = 0;
z = add(val);
split_val(root, x, y, val);
merge_new (x, x, z);
merge_new(root, x, y);
}
void del_new(int val) {
int x, y, z;
x = y = z = 0;
split_val(root, x, y, val);
split_val(x, x, z, val - 1);
merge_new(z, tree[z].left, tree[z].right);
merge_new(x, x, z);
merge_new(root, x, y);
}
void get_rank(int val) {
int x, y;
x = y = 0;
split_val(root, x, y, val - 1);
cout << tree[x].size + 1 << "\n";
merge_new(root, x, y);
}
void get_val(int rank) {
find_new(root, rank);
}
void get_pre(int val) {
int x, y;
x = y = 0;
split_val(root, x, y, val - 1);
find_new(x, tree[x].size);
merge_new(root, x, y);
}
void get_next(int val) {
int x, y;
x = y = 0;
split_val(root, x, y, val);
find_new(y, 1);
merge_new(root, x, y);
}
void rever(int l, int r) {
int a, b, c, d;
split_k(root, a, b, r);
split_k(a, c, d, l - 1);
tree[d].lazy ^= 1;
int rt;
merge_new(rt, c, d);
merge_new(root, rt, b);
}
int n, m;
int cnt = 1;
int flag = 0;
void print(int x) {
if (!x)return;
pushdown(x);
print(tree[x].left);
if (cnt == n && flag) return;
if (cnt != n) {
cout << tree[x].val << " ";
cnt++;
}
else {
cout << tree[x].val;
flag = 1;
}
print(tree[x].right);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
//int n, m;
cin >> n >> m;
memset(tree, 0, sizeof(tree));
add(MOD);
root = 1;
tree[root].size = 0;
for (int i = 1; i <= n; i++) {
insert_new(i);
}
for (; m; --m) {
int x, y;
cin >> x >> y;
rever(x, y);
}
print(1);
//cout << "\n";
return 0;
}