写的 fhq-treap

#include<bits/stdc++.h>
namespace fast_IO
{
	/**
    *略
	*/
};
using namespace fast_IO;
int n,m;
template <typename T>
inline void swap(T &_x,T &_y)
{
	T tmp=_x;
	_x=_y,_y=tmp;
}
struct node
{
	int sum,w,siz,lazy;
	node *lc,*rc;
	inline node(int sum)
	{
		this->sum=sum,w=rand(),siz=1,lazy=0,lc=rc=nullptr;
	}
	inline void pushup()
	{
		siz=(lc==nullptr?0:lc->siz)+(rc==nullptr?0:rc->siz)+1;
	}
	inline void pushdown()
	{
		if(lazy)
		{
			if(lc!=nullptr) lc->lazy^=1,swap(lc->lc,lc->rc);
			if(rc!=nullptr) rc->lazy^=1,swap(rc->lc,rc->rc);
			lazy=0;
		}
	}
};
class fhq_treap
{
private:
	node *root;
	inline node *merge(node *l,node *r)
	{
		if(l==nullptr) return r;
		if(r==nullptr) return l;
		if(l->w<r->w)
		{
			l->pushdown(),l->rc=merge(l->rc,r),l->pushup();
			return l;
		}else
		{
			r->pushdown(),r->lc=merge(l,r->lc),r->pushup();
			return r;
		}
	}
	inline std::pair<node *,node *> split(node *rt,const int &k)
	{
		std::pair<node *,node *> ret;
		if(rt==nullptr) return std::make_pair(nullptr,nullptr);
		rt->pushdown();
		int left=rt->lc==nullptr?0:rt->lc->siz;
		if(k<left) ret=split(rt->lc,k),rt->lc=ret.second,rt->pushup(),ret.second=rt;
		else ret=split(rt->rc,k-left-1),rt->rc=ret.first,rt->pushup(),ret.first=rt;
		return ret;
	}
	inline void print(node *rt)
	{
		if(rt==nullptr) return;
		rt->pushdown(),print(rt->lc),out<<rt->sum<<' ',print(rt->rc);
	}
public:
	inline void add(const int &sum)
	{
		node *ne=new node(sum);
		root=merge(root,ne);
	}
	inline void print()
	{
		print(root);
	}
	inline void overturn(const int &l,const int &r)
	{
		node *root1,*root2,*root3;
		std::pair<node *,node *> tmp;
		tmp=split(root,l-1),root1=tmp.first,root2=tmp.second;
		tmp=split(root2,r-l+1),root2=tmp.first,root3=tmp.second;
		root2->lazy^=1,swap(root2->lc,root2->rc),root=merge(merge(root1,root2),root3);
	}
};
fhq_treap tree;
int main()
{
	srand(time(0));
	in>>n>>m;
	for(int i=1;i<=n;i++) tree.add(i);
	for(int i=1,l,r;i<=m;i++) in>>l>>r,tree.overturn(l,r);
	tree.print();
	fwrite(Ouf,1,p3-Ouf,stdout),fflush(stdout);
	return 0;
}