P3391 【模板】文艺平衡树 非旋转的treap解法

P3391 【模板】文艺平衡树

//非旋转treap 
#include
using namespace std;
const int N=10e5+5;
int ch[N][2],tag[N],val[N],siz[N],key[N];
int tn,root,n,m;
inline void pushup(int x)
{
	siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
}
inline void pushdown(int x)
{
	if (x&&tag[x])
	{
		tag[x]^=1;
		swap(ch[x][0],ch[x][1]);
		if (ch[x][0]) tag[ch[x][0]]^=1;
		if (ch[x][1]) tag[ch[x][1]]^=1;
	}
}
inline int makenode(int x)
{
	++tn;siz[tn]=1;val[tn]=x;key[tn]=rand();return tn;
}
inline int merge(int x,int y)
{
	if(!x||!y) return x+y;
	pushdown(x),pushdown(y);
	if (key[x]>n>>m;
	for(int i=1;i<=n;i++)
	{
		root=merge(root,makenode(i));
	}
	//pre(root);
	while(m--)
	{
		int a,b;
		cin>>a>>b;
		rever(a,b);
	//	Inorder(root);
	//	cout<