「模板」 FHQ_Treap 区间翻转

<题目链接>

---

#include <algorithm>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

using std::swap;

const int MAXN=100010;

int n,m;

class FHQ_Treap

{

	public:

		FHQ_Treap(void)

		{

			rt=cnt=0;

			memset(a,0,sizeof a);

		}

		void Insert(int x)

		{

			s[++cnt]=node(x,Random(),1);

			Merge(rt,rt,cnt);

		}

		void Reverse(int x,int y)

		{

			int l=0,r=0,t=0;

			Split(rt,x-1,l,t),Split(t,y-x+1,t,r);

			s[t].lazy^=1,Merge(l,l,t),Merge(rt,l,r);

		}

		void Print(void)

		{

			DFS(rt),putchar('\n');

		}

	private:

		bool a[MAXN];

		int rt,cnt;

		struct node

		{

			int v,p,size,lazy,c[2];

			node(int _v=0,int _p=0,int _size=0)

			{

				v=_v,p=_p,size=_size,lazy=0;

				memset(c,0,sizeof c);

			}

		}s[MAXN];

		int Random(void)

		{

			int x;

			while(a[x=rand()%MAXN]);

			a[x]=1;

			return x;

		}

		void Update(int i)

		{

			s[i].size=s[s[i].c[0]].size+s[s[i].c[1]].size+1;

		}

		void PushDown(int i)

		{

			int &l=s[i].c[0],&r=s[i].c[1];

			swap(l,r);

			if(l)

				s[l].lazy^=1;

			if(r)

				s[r].lazy^=1;

			s[i].lazy=0;

		}

		void Split(int i,int x,int &l,int &r)

		{

			if(!i)

			{

				l=r=0;

				return;

			}

			if(s[i].lazy)

				PushDown(i);

			int t=s[s[i].c[0]].size+1;

			if(x<t)

				Split(s[r=i].c[0],x,l,s[i].c[0]);

			else

				Split(s[l=i].c[1],x-t,s[i].c[1],r);

			Update(i);

		}

		void Merge(int &i,int l,int r)

		{

			if(!l || !r)

			{

				i=l|r;

				return;

			}

			if(s[l].p>s[r].p)

			{

				if(s[l].lazy)

					PushDown(l);

				Merge(s[i=l].c[1],s[l].c[1],r);

			}

			else

			{

				if(s[r].lazy)

					PushDown(r);

				Merge(s[i=r].c[0],l,s[r].c[0]);

			}

			Update(i);

		}

		void DFS(int i)

		{

			if(s[i].lazy)

				PushDown(i);

			if(s[i].c[0])

				DFS(s[i].c[0]);

			printf("%d ",s[i].v);

			if(s[i].c[1])

				DFS(s[i].c[1]);

		}

}T;

int main(int argc,char *argv[])

{

	srand((unsigned)time(NULL));

	scanf("%d %d",&n,&m);

	for(int i=1;i<=n;++i)

		T.Insert(i);

	for(int i=1,l,r;i<=m;++i)

	{

		scanf("%d %d",&l,&r);

		T.Reverse(l,r);

	}

	T.Print();

	return 0;

}