记录编号	245271	评测结果	MMMMMMMMMM
题目名称	Travel	最终得分	0
用户昵称	zys	是否通过	未通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-04-02 19:00:34	内存使用	0.00 MiB

#define maxn 100050
#define L(x) ch[x][0]
#define R(x) ch[x][1]

#include<cstdio>
#include<cstdlib>

using namespace std;

bool rev[maxn];
int sta[100],ch[maxn][2],pos;
int n,m,fa[maxn],root,posl,posr,siz[maxn];

inline void Swap(int &x,int &y){if(x!=y)x^=y,y^=x,x^=y;}

inline void PushUp(int rt){if(rt)siz[rt]=siz[L(rt)]+siz[R(rt)]+1;}

inline void PushDown(int x)
{
	if(rev[x]&&x){
        rev[L(x)]^=1;rev[R(x)]^=1;
		Swap(L(x),R(x));rev[x]=false;
	}
}

inline void Rotate(int p,int d)
{
	int x=fa[p];fa[p]=fa[x];
	if(fa[x])ch[fa[x]][R(fa[x])==x]=p;
	fa[x]=p;ch[x][!d]=ch[p][d];
	if(ch[p][d])fa[ch[p][d]]=x;
	ch[p][d]=x;PushUp(x);
}

inline void Splay(int p,int f)
{
	sta[++sta[0]]=p;
	for(int i=p;i!=f;i=fa[i])
		sta[++sta[0]]=fa[i];
	while(sta[0])PushDown(sta[sta[0]--]);
	int x,y,d;
	while(fa[p]!=f){
		x=fa[p];y=fa[x];
		d=(R(x)==p);
		if(y==f)Rotate(p,!d);
		else{
			if(ch[y][d]==x)Rotate(x,!d),Rotate(p,!d);
			else Rotate(p,!d),Rotate(p,d);
		}
	}
	PushUp(p);
	if(!f)root=p;
}

int FindKth(int rt,int kth)
{
	PushDown(rt);
	if(siz[L(rt)]>=kth)return FindKth(L(rt),kth);
	else if(kth==siz[L(rt)]+1)return rt;
	else return FindKth(R(rt),kth-siz[L(rt)]-1);
}

inline void Reversal(int l,int r)
{
	posl=FindKth(root,l-1);
	posr=FindKth(root,r+1);
	Splay(posl,fa[root]);Splay(posr,posl);
	rev[L(R(root))]^=1;
}

inline int Delete(int l,int r)
{
	posl=FindKth(root,l-1);
	posr=FindKth(root,r+1);
	Splay(posl,fa[root]);Splay(posr,posl);
	int ret=L(posr);
	fa[L(posr)]=0;L(posr)=0;
	PushUp(posr);PushUp(posl);
	return ret;
}

inline void Insert(int l,int r,int p)
{
	posl=FindKth(root,l);
	posr=FindKth(root,r);
	Splay(posl,fa[root]);Splay(posr,posl);
	L(posr)=p;fa[p]=posr;PushUp(posr);PushUp(posl);
}

inline void solve(int a,int b,int c)
{
	Reversal(a+1+1,a+b+1);
	if(a==c)return;
	else Insert(c+1,c+1+1,Delete(a+1+1,a+b+1));
}

int build(int l,int r)
{
	int mid=(l+r)>>1;
	if(l<mid)L(mid)=build(l,mid-1);
	if(r>mid)R(mid)=build(mid+1,r);
	if(mid==1)L(mid)=n+1,siz[n+1]=1;
	if(mid==n)R(mid)=n+2,siz[n+2]=1;
	if(L(mid))fa[L(mid)]=mid;
	if(R(mid))fa[R(mid)]=mid;
	PushUp(mid);return mid;
}

void print(int rt)
{
	PushDown(rt);
	if(L(rt))print(L(rt));
	if(rt>=1&&rt<=n)printf("%d ",rt);
	if(R(rt))print(R(rt));
}

int main()
{
    freopen("travel_travel.in","r",stdin);
	freopen("travel_travel.out","w",stdout);
	scanf("%d%d",&n,&m);
	root=build(1,n);
	for(int i=1,a,b,c;i<=m;i++){
		scanf("%d%d%d",&a,&b,&c);
		solve(a,b,c);
	}
	print(root);
}