我们做 Splay 模板的 P3319 时，有个同学用了 WBLT，还跑得飞快。

我们老老实实打 Splay 的肯定不服啊，然后就绞尽脑汁卡常。

指针的数组的都试过了，拆开了封装好的结构体，函数甚至 inline 改 define，各种语言换着乱卡，快读快写已经想方设法把常数降到最低……

然后，没卡过……

求帮忙 QAQ。

目前 Code：

#include<cstdio>
#include<algorithm>
static char buf[10000000],*p1=buf,*p2=buf,obuf[10000000],*p3=obuf;
#define flush() fwrite(obuf,p3-obuf,1,stdout)
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,10000000,stdin),p1==p2)?EOF:*p1++
#define putchar(x) (p3-obuf<10000000)?(*p3++=x):(flush(),p3=obuf,*p3++=x)
inline void read(int& x){
	x=0;bool flag=0;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') flag=1;
	if(flag) for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)-(ch&15);
	else for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch&15);
}
inline void write(int x){
    static int sta[7];
    int top=0;
    do sta[top++]=x%10,x/=10;
    while(x);
    while(top) putchar(sta[--top]^48);
}
int n,m;
struct node{
	bool tag;
	int val,siz;
	node* fa;
	node* ch[2];
	node(){}
	node(int Val):val(Val),siz(1){}
	node(int Val,node* Fa):val(Val),siz(1),fa(Fa){}
};
node* root;
#define get_siz(p) ((p)?((p)->siz):0)
#define updata(p) (p)->siz=get_siz((p)->ch[0])+get_siz((p)->ch[1])+1
#define check(p) ((p)==((p)->fa)->ch[1])
#define clear(p) (p?((delete p),p=nullptr):(p=nullptr))
inline void push_down(node* p){
	if((!p)||(!(p->tag))) return;
	if(p->ch[0]) (p->ch[0])->tag^=1;
	if(p->ch[1]) (p->ch[1])->tag^=1;
	std::swap(p->ch[0],p->ch[1]);
	p->tag=0;
}
inline void rotate(node* p){
	node *fa=p->fa,*gra=fa->fa;
	bool chk=check(p);
	push_down(p),push_down(fa);
	fa->ch[chk]=p->ch[chk^1];
	if(p->ch[chk^1]) (p->ch[chk^1])->fa=fa;
	p->ch[chk^1]=fa,fa->fa=p,p->fa=gra;
	if(gra) gra->ch[fa==(gra->ch[1])]=p;
	updata(p),updata(fa);
}
inline void splay(node* p,node* rt){
	for(node* fa=p->fa;(fa=p->fa)!=rt;rotate(p)) if(fa->fa!=rt) rotate(check(p)==check(fa)?fa:p);
}
inline void splay(node* p){
	for(node* fa=p->fa;(fa=p->fa);rotate(p)) if(fa->fa) rotate(check(p)==check(fa)?fa:p);
	root=p;
}
inline node* kth(int rnk){
	node* p=root;
	while(1){
		push_down(p);
		if(p->ch[0]&&rnk<=get_siz(p->ch[0])) p=p->ch[0];
		else{
			rnk-=1+get_siz(p->ch[0]);
			if(rnk<=0) return splay(p),p;
			else p=p->ch[1];
		}
	}
}
inline void reverse(int& L,int& R){
	node *l=kth(L),*r=kth(R+2);
	splay(l);
	splay(r,root);
	node *p=(root->ch[1])->ch[0];
	p->tag^=1;
}
void print(node* p){
	if(!p) return;
	push_down(p);
	print(p->ch[0]);
	if((p->val)>=1&&(p->val)<=n) write(p->val),putchar(' ');
	print(p->ch[1]);
}
void build(node* &p,node* fa,int l,int r){
	if(l>r) return;
	int mid=(l+r)>>1;
	p=new node(mid,fa);
	build(p->ch[0],p,l,mid-1);
	build(p->ch[1],p,mid+1,r);
	updata(p);
}
signed main(){
	read(n),read(m);
	build(root,nullptr,0,n+1);
	for(int l,r;m--;) read(l),read(r),reverse(l,r);
	print(root);
	flush();
	return 0; 
}