Tyvj 1729 文艺平衡树

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
struct FhqTreap
{
	struct Node
	{
		int ch[2],siz,rev;
		ll key,val;
		void REV()
		{
			rev^=1,swap(ch[0],ch[1]);
		}
	};
	vector<Node> v;
	int root;
	FhqTreap():v(1),root(0) {}
	void push_down(int k)
	{
		if(!k)return;
		for(int i=0,*ch=v[k].ch; i<2; ++i)
			if(ch[i]&&v[k].rev)v[ch[i]].REV();
		v[k].rev=0;
	}
	void push_up(int k)
	{
		if(!k)return;
		v[k].siz=1;
		for(int i=0,*ch=v[k].ch; i<2; ++i)
			if(ch[i])
				v[k].siz+=v[ch[i]].siz;
	}
	int merge(int a,int b)
	{
		if(!a||!b)return a+b;
		if(v[a].key<v[b].key)
			return push_down(a),v[a].ch[1]=merge(v[a].ch[1],b),push_up(a),a;
		return push_down(b),v[b].ch[0]=merge(a,v[b].ch[0]),push_up(b),b;
	}
	void split(int a,int s,int &l,int &r)
	{
		if(!s)l=0,r=a;
		else if(v[v[a].ch[0]].siz<s)
			push_down(a),split(v[a].ch[1],s-v[v[a].ch[0]].siz-1,v[a].ch[1],r),push_up(l=a);
		else
			push_down(a),split(v[a].ch[0],s,l,v[a].ch[0]),push_up(r=a);
	}
	void push_back(ll d)
	{
		v.push_back(Node { {0,0},1,0,rand(),d});
		root=merge(root,v.size()-1);
	}
	void reverse(int l,int r)
	{
		int a,b,c;
		split(root,r,b,c),split(b,l-1,a,b),v[b].REV(),root=merge(merge(a,b),c);
	}
	void print(int u)
	{
		if(!u)return;
		push_down(u);
		print(v[u].ch[0]);
		printf("%d ",v[u].val);
		print(v[u].ch[1]);
	}
};
int main()
{
	int n,m;
	FhqTreap t;
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; ++i)t.push_back(i);
	for(int i=1,l,r; i<=m; ++i)scanf("%d%d",&l,&r),t.reverse(l,r);
	t.print(t.root);
}