今天用 FHQ 写 文艺平衡树板子，可是发现一个问题就是答案是随机的，我每次操作输出了一下树就没有问题，可是一旦放在末尾输出就有问题了，我认为大致是推懒标记的问题，但我看了半个下午也没发现问题，哪位大佬能帮蒟蒻看看是哪里的问题（应该是推懒标记之类的问题）。

我的代码：

#include<bits/stdc++.h>

using namespace std;

struct node
{
	int ls, rs;
	int key, pri;
	int size;
	int lazy;
};

int n, m;
node tree[100010];
int idx;
int root;
int ans;
int last;

void add_node(int x)
{
	idx ++;
	tree[idx].ls = tree[idx].rs = 0;
	tree[idx].key = x;
	tree[idx].pri = rand();
	tree[idx].size = 1;
}

void update(int u)
{
	tree[u].size = tree[tree[u].ls].size + tree[tree[u].rs].size + 1;
}

void pushdown(int u)
{
	if(tree[u].lazy)
	{
		swap(tree[u].ls, tree[u].rs);
		tree[tree[u].ls].lazy ^= 1;
		tree[tree[u].rs].lazy ^= 1;
		tree[u].lazy = 0;
	}
}

void split(int u, int x, int &L, int &R)
{
	if(u == 0)
	{
		L = R = 0;
		return;
	}
	pushdown(u);
	if(tree[tree[u].ls].size >= x)
	{
		R = u;
		split(tree[u].ls, x, L, tree[u].ls);
	}
	else
	{
		L = u;
		split(tree[u].rs, x - tree[tree[u].ls].size - 1, tree[u].rs, R);
	}
	update(u);
}

int merge(int L, int R)
{
	if(L == 0) return R;
	if(R == 0) return L;
	pushdown(L);
	pushdown(R);
	if(tree[L].pri > tree[R].pri)
	{
		tree[L].rs = merge(tree[L].rs,R);
		update(L);
		return L;
	}
	else
	{
		tree[R].ls = merge(L,tree[R].ls);
		update(R);
		return R;
	}
}

void insert(int x)
{
	int l, r;
	split(root, x, l, r);
	add_node(x);
	int kkk = merge(l, idx);
	root = merge(kkk, r);
}

void out(int u)
{
	if(u == 0) return;
	pushdown(u);
	out(tree[u].ls);
	cout << tree[u].key << " ";
	out(tree[u].rs);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	srand(time(0));
	cin >> n >> m;
	for(int i = 1;i <= n;i ++)
	{
		insert(i);
	}
	for(int i = 1;i <= m;i ++)
	{
		int x, y;
		cin >> x >> y;
		int l, r, p;
		split(root, y, l, r);
		split(l, x - 1, l, p);
		tree[p].lazy ^= 1;
		root = merge(merge(l, p), r);
	}
	out(root);
	cout << "\n"; 
	return 0;
}

/*
8 5
3 7
4 6
1 4
6 8
3 6
1 2 7 6 5 4 3 8
1 2 5 6 7 4 3 8
6 5 2 1 7 4 3 8
6 5 2 1 7 8 3 4
6 5 8 7 1 2 3 4
*/