无旋Treap求调

#include <bits/stdc++.h>
#define rank rnk
#define mod 20130426
using namespace std;

struct node
{
	int val, size, rnd, cnt, lazy;
	int ch[2];
}t[1000100];

int cnt, rt;

int newnode(int val)
{
	cnt++;
	t[cnt].cnt = t[cnt].size = 1;
	t[cnt].rnd = rand();
	t[cnt].val = val;
	return cnt;
}

void update(int id)
{
	t[id].size = t[t[id].ch[0]].size + t[t[id].ch[1]].size + t[id].cnt;
	return;
}

void pushdown(int id)
{
	if(t[id].lazy)
	{
		t[t[id].ch[0]].lazy ^= 1;
		t[t[id].ch[1]].lazy ^= 1;
		swap(t[id].ch[0], t[id].ch[1]);
		t[id].lazy = 0;
	}
}

int merge(int x, int y)
{
	if(!x || !y)return x + y;
	pushdown(x);
	pushdown(y);
	if(t[x].rnd <= t[y].rnd)
	{
		pushdown(x);
		t[x].ch[1] = merge(t[x].ch[1], y);
		update(x);
		return x;
	}
	else
	{
		pushdown(y);
		t[y].ch[0] = merge(x, t[y].ch[0]);
		update(y);
		return y;
	}
}

void splitk(int k, int id, int &x, int &y)
{
	if(id == 0)
	{
		x = y = 0;
		return;
	}
	int lsize = t[t[id].ch[0]].size;
	pushdown(id);
	if(lsize >= k)
	{
		y = id;
		pushdown(y);
		splitk(k, t[y].ch[0], x, t[y].ch[0]);		
	}
	else
	{
		x = id;
		pushdown(x);
		splitk(k - lsize - 1, t[x].ch[1], t[x].ch[1], y);
	}
	update(id);
}

void query(int id)
{
	if(id == 0)return;
	pushdown(id);
	query(t[id].ch[0]);
	cout << t[id].val << " ";
	query(t[id].ch[1]);
}
void reverse(int l, int r)
{
	int x = 0, y = 0, z = 0;
	splitk(rt, l, x, y);
	splitk(y, r - l + 1, y, z);
	t[y].lazy ^= 1;
	rt = merge(merge(x, y), z);
}

signed main()
{
	srand(536);
	int n, m;
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
	{
		rt = merge(rt, newnode(i));
	}
//	cout << rt << "\n";
//	for(int i = 1;i <= n;i++)
//	{
//		cout << t[i].val << " " << t[i].ch[0] << " " << t[i].ch[1] << " " << t[i].size << " " << t[i].lazy << "\n";
//	}
	while(m--)
	{
		int l, r;
		cin >> l >> r;
		reverse(l, r);
//		cout << rt << "\n";
//		for(int i = 1;i <= n;i++)
//		{
//			cout << t[i].val << " " << t[i].ch[0] << " " << t[i].ch[1] << " " << t[i].size << " " << t[i].lazy << "\n";
//		}
	}
	query(rt);
	return 0;
}