无旋treap 文艺平衡树

    因为需要用到区间修改，所以该用splay（尚未填坑）或者无旋treap（刚刚填上）

     最开始的建树用到了建笛卡尔树的方法，把id大于当前点的点不断出栈，又因为这道题的点是按序入栈的，所以当它无法让更多点出栈时，他就是栈首的右子树，而最后一个出栈的点，就是当前点的左子树。显然root=zhan[1]。

    

#include<stdio.h>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#define inf 10000000
using namespace std;
int n,m;
struct treap
{
	treap* ch[2];
	int id,h,lazy,size;
	treap(){size=lazy=h=0;id=rand();ch[1]=ch[0]=NULL;}
	inline void update(){size=ch[0]->size+ch[1]->size+1;}
} *null=new treap(),*root=null,*zhan[100005],*x,*last;
typedef pair<treap*,treap*> D;
inline int read()
{
	int sum=0,f=1;char x=getchar();
	while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
	while(x>='0'&&x<='9'){sum=sum*10+x-'0';x=getchar();}
	return sum*f;
}
inline treap* newtreap(int x)
{
	treap *o=new treap();
	o->size=1;o->h=x;
	o->ch[0]=o->ch[1]=null;
	return o;
}
void push(treap *f)
{
	if(f==null)return;
	if(f->lazy)
	{
		f->lazy^=1;
		if(f->ch[0]!=null)f->ch[0]->lazy^=1;
		if(f->ch[1]!=null)f->ch[1]->lazy^=1;
		swap(f->ch[0],f->ch[1]);
	}
}
D split(treap *f,int k)
{
	if(f==null)return  D(null,null);
	push(f);D y;
	if(f->ch[0]->size>=k)
	    {y=split(f->ch[0],k);f->ch[0]=y.second;f->update();y.second=f;}
	else
	    {y=split(f->ch[1],k-f->ch[0]->size-1);f->ch[1]=y.first;f->update();y.first=f;}    
	return y;
}
treap* merge(treap *a,treap *b)
{
	if(a==null)return b;
	if(b==null)return a;
	push(a);push(b);
	if(a->id<b->id)
	     {a->ch[1]=merge(a->ch[1],b);a->update();return a;}
	else
	     {b->ch[0]=merge(a,b->ch[0]);b->update();return b;}
}
void dfs(treap *x)
{
	if(x==null)return;
	push(x);
	if(x->ch[0]!=null)dfs(x->ch[0]);
	printf("%d ",x->h);
	if(x->ch[1]!=null)dfs(x->ch[1]);
}
int yjn()
{
	 freopen("sph.in","r",stdin);
    freopen("sph.out","w",stdout);
	scanf("%d%d",&n,&m);
	int p=0;
	for(int i=1;i<=n;i++)
	{
		x=newtreap(i);last=null;
		while(p&&zhan[p]->id>x->id)
		{zhan[p]->update();last=zhan[p];zhan[p--]=null;}
		if(p)zhan[p]->ch[1]=x;
		x->ch[0]=last;zhan[++p]=x;
	}
	while(p)zhan[p--]->update();
	root=zhan[1];
	int l,r;
	for(int i=1;i<=m;i++)
	{
		l=read();r=read();
		D x=split(root,r);
		D y=split(x.first,l-1);
		if(y.second!=null)y.second->lazy^=1;
		root=merge(merge(y.first,y.second),x.second);
	}
	dfs(root);
}
int qty=yjn();
int main(){;}