平衡树

二分查找树（ BST ）

(operatorname{BST}) 树满足性质：

每一个节点关键码 不小于 它 左子树中 任意节点关键码。
每一个节点关键码 不大于 它 右子树中 任意节点关键码。
整棵树 中序遍历单调递增 。

建立：由两个节点（ (+inf~&~-inf) ）构成。
查询：从根开始一个个比较，逐渐来到查询的点。
插入：若已经有了这个点，那么 (cnt++) ；否则新建一个叶子节点。与查询操作类似。
前驱（后继）：先向左（右）走，在一直往右（左）走，直至不能走为止。
删除：
- 只有左子树或右子树：直接删除 (x) ，令 (x) 的子节点代替 (x) 的位置。
- 既有左子树又有右子树：在 (x) 子树中找出 (x) 的后继 (next) ，令 (next) 代替 (x) 的位置，删除 (next) 。

期望复杂度 (O(log~n)) ，但是极易退化为 (O(n)) 。

Treap

即在 (operatorname{BST}) 的基础上加入旋转操作。

每一个节点仅记录了左右子节点，不记录父亲节点。(operatorname{Treap}) 通过左旋（ (operatorname{zag}) ）和右旋（ (operatorname{zig}) ），通过 随机数据 保持平衡。(operatorname{Treap}) 给每一个节点赋予了一个随机值，用来满足堆性质。

对于插入操作：同 (operatorname{BST}) 的加入方式，自下而上依次检查，当某个节点不满足大根堆性质时就进行单旋操作。

特别对于删除操作：

如果只有一个儿子：用它的儿子代替它并替代它。
若果有两个儿子：把需要删除的节点旋转到只有一个儿子。

总而言之：(operatorname{Treap}) 通过适当的单旋操作，在 维持关键码满足 (operatorname{BST}) 性质 的同时，还 使每个节点上生成的额外权值满足大根堆性质 。

复杂度：都是 (O(log~n))

P3369 【模板】普通平衡树（弱化版）

对于这道题，要求查询排名，则给每一个节点增加一个值 (size) ，在进行 (ratate) 操作时也要对 (size) 进行更改。

因为要对 (size) 进行修改，所以查询操作用递归的形式。

$ ext{Treap}$ 模板代码

#include<bits/stdc++.h>
using namespace std;
#define infll 0x3f3f3f3f3f3f3f3f
#define inf 0x7f7f7f7f
#define Maxn 200005
typedef long long ll;
inline int rd()
{
	 int x=0;
     char ch,t=0;
     while(!isdigit(ch = getchar())) t|=ch=='-';
     while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
     return x=t?-x:x;
}
int n,m,tot,root;
int a[Maxn],b[Maxn];
struct treap
{
	 int randval,val;
	 int ls,rs;
	 int cnt,siz;
}tree[Maxn];
void pushup(int p)
{
	 tree[p].siz=tree[p].cnt+tree[tree[p].ls].siz+tree[tree[p].rs].siz;
}
int New(int val)
{
	 tree[++tot].val=val,tree[tot].randval=rand();
	 tree[tot].cnt=tree[tot].siz=1;
	 tree[tot].ls=tree[tot].rs=0;
	 return tot;
}
void build()
{
	 New(-inf),New(inf);
	 tree[1].rs=2,root=1;
	 pushup(root);
}
void zag(int &x) // Make ls turn right
{
	 int p=tree[x].ls;
	 tree[x].ls=tree[p].rs,tree[p].rs=x;
	 pushup(x),pushup(p),x=p;
}
void zig(int &x) // Make rs turn left
{
	 int p=tree[x].rs;
	 tree[x].rs=tree[p].ls,tree[p].ls=x;
	 pushup(x),pushup(p),x=p;
}
void Insert(int &p,int val)
{
	 if(!p) { p=New(val); return; }
	 if(val==tree[p].val) { tree[p].cnt++; pushup(p); return; } // 别忘了 pushup 
	 if(val<tree[p].val)
	 {
	 	 Insert(tree[p].ls,val);
	 	 if(tree[p].randval<tree[tree[p].ls].randval) zag(p);
	 }
	 else
	 {
	 	 Insert(tree[p].rs,val);
	 	 if(tree[p].randval<tree[tree[p].rs].randval) zig(p);
	 }
	 pushup(p);
}
void del(int &p,int val)
{
	 if(!p) return;
	 if(val==tree[p].val)
	 {
	 	 if(tree[p].cnt>1) { tree[p].cnt--; pushup(p); return; } // 别忘了 pushup 
	 	 if(tree[p].ls || tree[p].rs)
	 	 {
	 	 	 if(tree[p].rs==0 || tree[tree[p].ls].randval>tree[tree[p].rs].randval)
			   	 zag(p),del(tree[p].rs,val); // 保持大根堆性质 
	 	 	 else zig(p),del(tree[p].ls,val);
	 	 	 pushup(p);
		 }
		 else p=0;
		 return;
	 }
	 if(val<tree[p].val) del(tree[p].ls,val);
	 else del(tree[p].rs,val);
	 pushup(p);
}
int query_val(int p,int rank)
{
	 if(!p) return inf;
	 if(tree[tree[p].ls].siz>=rank) return query_val(tree[p].ls,rank);
	 if(tree[tree[p].ls].siz+tree[p].cnt>=rank) return tree[p].val;
	 return query_val(tree[p].rs,rank-tree[tree[p].ls].siz-tree[p].cnt);
}
int query_rank(int p,int val)
{
	 if(!p) return 0;
	 if(val==tree[p].val) return tree[tree[p].ls].siz+1;
	 if(val<tree[p].val) return query_rank(tree[p].ls,val);
	 return query_rank(tree[p].rs,val)+tree[tree[p].ls].siz+tree[p].cnt;
}
int pre(int val)
{
	 int p=root,ans=1; // 无穷小 
	 while(p)
	 {
	 	 if(val==tree[p].val)
	 	 {
	 	 	 if(tree[p].ls)
			 {
			 	 for(p=tree[p].ls;tree[p].rs;p=tree[p].rs);
			 	 ans=p;
			 }
			 break;
		 }
		 if(tree[p].val<val && tree[p].val>tree[ans].val) ans=p; // 及时更新 
		 if(val<tree[p].val) p=tree[p].ls;
		 else p=tree[p].rs;
	 }
	 return tree[ans].val;
}
int nex(int val)
{
	 int p=root,ans=2; // 无穷大 
	 while(p)
	 {
	 	 if(val==tree[p].val)
	 	 {
	 	 	 if(tree[p].rs)
	 	 	 {
	 	 	 	 for(p=tree[p].rs;tree[p].ls;p=tree[p].ls);
	 	 	 	 ans=p;
			 }
			 break;
		 }
		 if(tree[p].val>val && tree[p].val<tree[ans].val) ans=p;
		 if(val<tree[p].val) p=tree[p].ls;
		 else p=tree[p].rs;
	 }
	 return tree[ans].val;
}
int main()
{
     //freopen(".in","r",stdin);
     //freopen(".out","w",stdout);
	 n=rd(),build();
	 int opt,x;
	 for(int i=1;i<=n;i++)
	 {
	 	 opt=rd(),x=rd();
	 	 if(opt==1) Insert(root,x);
	 	 if(opt==2) del(root,x);
	 	 if(opt==3) printf("%d
",query_rank(root,x)-1);
	 	 if(opt==4) printf("%d
",query_val(root,x+1));
	 	 if(opt==5) printf("%d
",pre(x));
	 	 if(opt==6) printf("%d
",nex(x));
	 }
     //fclose(stdin);
     //fclose(stdout);
     return 0;
}

Splay

两种写法

综合上述情况，决定写两份模板代码（暂时只用了 namespace ）

代码中特别要注意的地方

查找 (x) 的前、后驱时要判断有无 (val) 为 (x) 的节点！不能直接返回前、后驱。
记得每次操作进行中、进行后（视不同函数而定）( ext{Splay})
清楚数组下标是节点编号，不是 (val)
及时 ( ext{update}) 更新信息
父子节点之间有双向的连接，缺一不可
（ ( ext{kth}) 中）要判断查询的 $k $是否正好为 (siz[ls]+dots) 所以应该判断 (kle 0)
（ ( ext{del}) 中）清楚 (root) 以及各种信息的更改顺序，防止在赋值之前信息已经被清空
（ ( ext{del}) 中）删除有两个儿子的根节点是应该先 ( ext{Splay}) 前驱 (pre()) ，再连接右子树。
- （在 ( ext{Splay(pre())}) 后，(pre()) 成为根的同时原先的根 (rt) 会成为根的右儿子，同时 (rt) 原先的右儿子会变为左儿子）
（ ( ext{Rank}) 中）在没有 (val) 为 (x) 的节点是返回 (1)
（ ( ext{Rank}) 中）(rank) 是比 (x) 小的个数 (+1) ！！！
（ ( ext{Rank}) 中）查找节点时小心子节点是空的！此时直接返回
（ ( ext{Splay}) 中）如果节点 (x) 已经在根节点，不需要修改。
（ ( ext{Splay},dots) 中）及时更新 (root)

伸展树（即 ( ext{Splay}) ）可以用于维护数与数之间的关系，也可以用于维护区间上的问题。

如果出现类似【模板】普通平衡树一样处理第 (k) 大数、排名等，需要在 ( ext{Insert}) 等操作中合并节点，成为一颗以权值关键字的类 ( ext{BST}) ，方便查找第几大之类。

一般使用的函数：

( ext{Insert}) ：按照权值大小找到应该插入的位置插入节点。
( ext{Del}) ：删去一个权值为 (val) 的数。
( ext{kth}) ：即所有数中第 (k) 大的数。
( ext{Rank}) ：这一个数的排名（比这个数小的数的个数加一）。

$ ext{Splay}$ 模板 $1$

namespace splay_number
{
	 int root,siz,ch[Maxn][2],fa[Maxn];
	 struct Node { ll val; int cnt,siz; int lay; }tree[Maxn];
	 #define ls ch[x][0]
	 #define rs ch[x][1]
	 inline int get(int x) { return x==ch[fa[x]][1]; }
	 inline void init(int x) { ls=rs=fa[x]=tree[x].cnt=tree[x].val=tree[x].siz=0; }
	 inline void pushup(int x)
 	 {
		 tree[x].siz=tree[ls].siz+tree[rs].siz+tree[x].cnt;
		 // 根据更新父节点信息 
	 }
	 inline void pushdown(int x){}
	 inline void rotate(int x)
	 {
		 register int y=fa[x],z=fa[y],k=get(x);
		 pushdown(y),pushdown(x);
		 ch[y][k]=ch[x][k^1];
		 if(ch[x][k^1]) fa[ch[x][k^1]]=y;
		 fa[y]=x,ch[x][k^1]=y,fa[x]=z;
		 if(z) ch[z][y==ch[z][1]]=x;
		 pushup(y),pushup(x);
	 }
	 inline void splay(int x,int rt=0)
	 {
		 if(x==rt) return;
		 for(int f=fa[x];f!=rt;rotate(x),f=fa[x])
		 	 if(fa[f]!=rt) rotate((get(f)==get(x))?f:x);
		 if(!rt) root=x;
	 }
	 inline int pre() { int x=ch[root][0]; while(rs) x=rs; return x; }
	 inline int nex() { int x=ch[root][1]; while(ls) x=ls; return x; }
	 inline int kth(int k)
	 {
		 for(register int x=root;x;)
		 {
		 	 pushdown(x);
		 	 if(ls && k<=tree[ls].siz) x=ls;
		 	 else
		 	 {
		 	 	 k-=tree[x].cnt+tree[ls].siz;
		 	 	 if(k<=0) return x; // 一般返回下标，如非特殊情况不改为其他 
		 	 	 x=rs;
			 }
		 }
		 return 0;
	 }
	 inline int Rank(ll val)
	 {
		 register int ret=0,x;
		 for(x=root;x;)
		 {
		 	 if(val<tree[x].val) { if(!ls) { ret+=1; break; } x=ls; }
		 	 else if(val==tree[x].val) { ret+=tree[ls].siz+1; break; }
		 	 else
		 	 {
		 	 	 ret+=tree[ls].siz+tree[x].cnt;
		 	 	 if(!rs) { ret+=1; break; }
		 	 	 x=rs;
			 }
		 }
		 splay(x);
		 return ret?ret:1;
	 }
	 inline void Insert(ll x)
	 {
		 register int cur=root,f=0;
		 while(cur && tree[cur].val!=x) f=cur,cur=ch[cur][x>tree[cur].val];
		 if(cur) tree[cur].cnt++;
		 else
		 {
		 	 cur=++siz;
		 	 if(f) ch[f][x>tree[f].val]=cur;
		 	 init(cur);
		 	 tree[cur].val=x,fa[cur]=f;
		 	 tree[cur].siz=tree[cur].cnt=1;
		 }
		 splay(cur);
	 }
	 inline void Del(ll val)
	 {
		 Rank(val); // 可以根据所得到的信息改为 kth 等 
		 register int cur=root;
		 if(tree[root].cnt>1) tree[root].cnt-=1,pushup(root);
		 else if(!ch[root][0] && !ch[root][1]) init(root),root=0;
		 else if(!ch[root][0]) root=ch[root][1],fa[root]=0,init(cur);
		 else if(!ch[root][1]) root=ch[root][0],fa[root]=0,init(cur);
		 else
		 {
		 	 int Last=pre();
		 	 splay(Last);
			 ch[Last][1]=ch[cur][1];
		 	 fa[ch[cur][1]]=Last;
			 init(cur); // 注意顺序！！ 
			 pushup(Last);
		 }
	 }
	 inline int Seperate(int l,int r) { l=kth(l),r=kth(r+2),splay(l,0),splay(r,l); return ch[r][0]; }
	 void print(int p) // 调试 
	 {
		 pushdown(p);
		 if(ch[p][0]) print(ch[p][0]);
		 printf("%lld ",tree[p].val);
		 if(ch[p][1]) print(ch[p][1]);
	 }
}
using namespace splay_number;

但是如果出现【模板】文艺平衡树、[NOI2005] 维护数列等用于区间查询、翻转等操作时，我们将原数组中的下标作为关键字，使用 ( ext{build}) 操作加入节点。

一般使用的函数：

( ext{build}) ：用于建立一段区间（非常平衡的完全二叉树），可以用去加入一段区间。
( ext{Find}) （即上一种情况中的 (kth) ）：用在区间数上变为了找到整个序列从左到右的第 (val) 个数，将它旋转的根。
( ext{split}) ：提取出一段区间。

$ ext{Splay}$ 模板 $2$

namespace splay_segment
{
	 int root,All,ch[Maxn][2],fa[Maxn];
	 int id[Maxn],a[Maxn];
	 queue<int> q; // 冗余节点回收 
	 struct Node { int siz,val,MAX,l_MAX,r_MAX,sum,chan_tag,rev_tag; }tree[Maxn];
	 #define ls ch[x][0]
	 #define rs ch[x][1]
	 inline int get(int x) { return x==ch[fa[x]][1]; }
	 inline void init(int x) { ls=rs=fa[x]=tree[x].chan_tag=tree[x].rev_tag=0; }
	 inline int pre() { int x=ch[root][0]; while(rs) x=rs; return x; }
	 inline int nex() { int x=ch[root][1]; while(ls) x=ls; return x; }
	 void recycle(int x) { if(!x) return; recycle(ls),recycle(rs),init(x),q.push(x); }
	 inline void pushup(int x)
 	 {
		 tree[x].siz=tree[ls].siz+tree[rs].siz+1;
		 tree[x].sum=tree[ls].sum+tree[rs].sum+tree[x].val;
		 tree[x].MAX=max(tree[ls].r_MAX+tree[x].val+tree[rs].l_MAX,max(tree[ls].MAX,tree[rs].MAX));
		 tree[x].l_MAX=max(tree[ls].l_MAX,tree[ls].sum+tree[x].val+tree[rs].l_MAX);
		 tree[x].r_MAX=max(tree[rs].r_MAX,tree[rs].sum+tree[x].val+tree[ls].r_MAX);
	 }
	 inline void pushdown(int x)
	 {
	 	 if(tree[x].chan_tag)
		 // 注意区间赋值的 tag 只能为 1 或 0 不能赋值为 val 
	 	 {
	 	 	 register int tmp=tree[x].val; tree[x].chan_tag=0;
	 	 	 if(ls)
	 	 	 {
	 	 	 	 tree[ls].chan_tag=1,tree[ls].val=tmp,tree[ls].sum=tmp*tree[ls].siz;
	 	 	 	 if(tmp>0) tree[ls].MAX=tree[ls].l_MAX=tree[ls].r_MAX=tree[ls].sum;
	 	 	 	 else tree[ls].MAX=tmp,tree[ls].l_MAX=tree[ls].r_MAX=0;
			 }
			 if(rs)
			 {
	 	 	 	 tree[rs].chan_tag=1,tree[rs].val=tmp,tree[rs].sum=tmp*tree[rs].siz;
	 	 	 	 if(tmp>0) tree[rs].MAX=tree[rs].l_MAX=tree[rs].r_MAX=tree[rs].sum;
	 	 	 	 else tree[rs].MAX=tmp,tree[rs].l_MAX=tree[rs].r_MAX=0;
			 }
		 }
		 if(tree[x].rev_tag)
		 {
		 	 tree[x].rev_tag=0;
		 	 if(ls) tree[ls].rev_tag^=1;
		 	 if(rs) tree[rs].rev_tag^=1;
		 	 swap(ch[ls][0],ch[ls][1]),swap(tree[ls].l_MAX,tree[ls].r_MAX);
		 	 swap(ch[rs][0],ch[rs][1]),swap(tree[rs].l_MAX,tree[rs].r_MAX);
		 }
	 }
	 inline void rotate(int x)
	 {
		 register int y=fa[x],z=fa[y],k=get(x);
		 pushdown(y),pushdown(x);
		 ch[y][k]=ch[x][k^1];
		 if(ch[x][k^1]) fa[ch[x][k^1]]=y;
		 fa[y]=x,ch[x][k^1]=y,fa[x]=z;
		 if(z) ch[z][y==ch[z][1]]=x;
		 pushup(y),pushup(x);
	 }
	 inline void splay(int x,int rt=0)
	 {
		 if(x==rt) return;
		 for(int f=fa[x];f!=rt;rotate(x),f=fa[x])
		 	 if(fa[f]!=rt) rotate((get(f)==get(x))?f:x);
		 if(!rt) root=x;
	 }
	 inline int Find(int k)
	 {
		 for(register int x=root;x;)
		 {
		 	 pushdown(x);
		 	 if(ls && k<=tree[ls].siz) x=ls;
		 	 else
		 	 {
		 	 	 k-=tree[ls].siz+1;
		 	 	 if(k<=0) return x;
		 	 	 x=rs;
			 }
		 }
		 return 0;
	 }
	 inline int split(int l,int r) { l=Find(l),r=Find(r+2),splay(l,0),splay(r,l); return ch[r][0]; }
	 int build(int F,int nl,int nr)
	 {
		 int mid=(nl+nr)>>1,x=id[mid],fx=id[F];
		 if(nl==nr)
		 {
		 	 tree[x].siz=1,tree[x].MAX=tree[x].sum=tree[x].val=a[mid];
		 	 tree[x].l_MAX=tree[x].r_MAX=max(a[mid],0);
		 }
		 if(nl<mid) ch[x][0]=build(mid,nl,mid-1);
		 if(mid<nr) ch[x][1]=build(mid,mid+1,nr);
		 tree[x].val=a[mid],fa[x]=fx,pushup(x);
		 return x;
	 }
	 inline void Insert(int pos,int tot)
	 {
	 	 for(int i=1;i<=tot;i++) a[i]=rd();
	 	 for(int i=1;i<=tot;i++)
	 	 	 if(!q.empty()) id[i]=q.front(),q.pop();
	 	 	 else id[i]=++All;
	 	 int rt=build(0,1,tot),l=Find(pos+1),r=Find(pos+2);
	 	 splay(l,0),splay(r,l),fa[rt]=r,ch[r][0]=rt;
		 pushup(r),pushup(l);
	 }
	 inline void Delete(int l,int r)
	 {
	 	 int rt=split(l,r),F=fa[rt];
	 	 recycle(rt),ch[F][0]=0;
		 pushup(F),pushup(fa[F]);
	 }
	 inline void change(int l,int r,int c)
	 {
	 	 int rt=split(l,r);
		 tree[rt].chan_tag=1,tree[rt].val=c,tree[rt].sum=c*tree[rt].siz;
		 if(c>0) tree[rt].MAX=tree[rt].l_MAX=tree[rt].r_MAX=tree[rt].sum;
		 else tree[rt].MAX=c,tree[rt].l_MAX=tree[rt].r_MAX=0;
		 pushup(fa[rt]),pushup(fa[fa[rt]]);
	 }
	 inline void Reverse(int l,int r)
	 {
	 	 int x=split(l,r);
	 	 tree[x].rev_tag^=1;
	 	 swap(ls,rs),swap(tree[x].l_MAX,tree[x].r_MAX);
	 	 pushup(fa[x]),pushup(fa[fa[x]]);
	 }
	 inline int query_sum(int l,int r) { return tree[split(l,r)].sum; }
	 inline int query_MAX(int l,int r) { return tree[split(l,r)].MAX; }
	 void print(int x) { if(!x) return; pushdown(x),print(ls),printf("%d ",tree[x].val),print(rs); }
}
// 任何修改操作都要反馈到根！！！ 
using namespace splay_segment;

应用 ( ightarrow) ( ext{LCT}) 预备知识 P3391 【模板】文艺平衡树

FHQ 非旋 Treap

FHQ-Treap学习笔记——万万没想到

（这里都用了 struct 封装）

模板 $1$

struct FQH_number
{
	 #define ls tree[p].pl
	 #define rs tree[p].pr
	 int All,root;
	 queue<int> Trash; // 回收站（垃圾桶） 
	 struct NODE { int pl,pr,siz,rnd; ll val; } tree[Maxn];
	 inline void init(int p)
	 	 { tree[p].rnd=rand(); ls=rs=0; tree[p].siz=1; }
	 inline int New(ll val)
	 {
	 	 int ret;
	 	 if(!Trash.empty()) ret=Trash.front(),Trash.pop();
		 else ret=++All;
		 init(ret),tree[ret].val=val;
		 return ret;
	 }
	 inline void pushup(int p)
	 	 { tree[p].siz=tree[ls].siz+tree[rs].siz+1; }
	 void split(int p,ll val,int &x,int &y)
	 {
	 	 if(!p) { x=y=0; return; }
	 	 if(tree[p].val<=val) x=p,split(rs,val,rs,y);
	 	 else y=p,split(ls,val,x,ls);
	 	 pushup(p);
	 }
	 int merge(int x,int y)
	 {
	 	 if(!x || !y) return x|y;
	 	 if(tree[x].rnd<tree[y].rnd)
		 	 { tree[x].pr=merge(tree[x].pr,y),pushup(x); return x; }
		 else
		 	 { tree[y].pl=merge(x,tree[y].pl),pushup(y); return y; }
	 }
 	 int x,y,z;
	 inline void Insert(ll val)
	 	 { split(root,val,x,y),root=merge(merge(x,New(val)),y); }
	 inline void Delete_All(ll val)
	 	 { split(root,val,z,x),split(x,val-1,x,y),root=merge(x,z); }
	 inline void Delete_one(ll val)
	 {
	 	 split(root,val,x,z),split(x,val-1,x,y);
	 	 Trash.push(y),y=merge(tree[y].pl,tree[y].pr);
	 	 root=merge(merge(x,y),z);
	 }
	 inline int Rank(ll val)
	 {
	 	 split(root,val-1,x,y);
	 	 int ret=tree[x].siz+1;
	 	 root=merge(x,y);
	 	 return ret;
	 }
	 inline int kth(int p,int k) // attention！！这里返回的是下标 
	 {
	 	 while(p)
	 	 {
	 	 	 if(k<=tree[ls].siz) p=ls;
	 	 	 else if(k==tree[ls].siz+1) break;
	 	 	 else k-=tree[ls].siz+1,p=rs;
		 }
		 return p;
	 }
	 inline ll pre(ll val)
	 {
	 	 split(root,val-1,x,y);
	 	 ll ret=tree[kth(x,tree[x].siz)].val;
	 	 root=merge(x,y);
	 	 return ret;
	 }
	 inline ll nex(ll val)
	 {
	 	 split(root,val,x,y);
	 	 ll ret=tree[kth(y,1)].val;
	 	 root=merge(x,y);
	 	 return ret;
	 }
}T1;

版本 $2$ （还不能够实现巨大多操作，留坑待填）

struct FHQ_segment
{
	 #define ls tree[p].pl
	 #define rs tree[p].pr
	 int All,root;
	 queue<int> Trash; // 回收站（垃圾桶） 
	 struct NODE { int pl,pr,siz,rnd,tag; ll val; } tree[Maxn];
	 inline void init(int p)
	 	 { tree[p].rnd=rand(); ls=rs=tree[p].tag=0; tree[p].siz=1; }
	 inline int New(ll val)
	 {
	 	 int ret;
	 	 if(!Trash.empty()) ret=Trash.front(),Trash.pop();
		 else ret=++All;
		 init(ret),tree[ret].val=val;
		 return ret;
	 }
	 inline void pushup(int p)
	 	 { tree[p].siz=tree[ls].siz+tree[rs].siz+1; }
	 inline void pushdown(int p)
	 {
	 	 if(tree[p].tag)
	 	 {
	 	 	 swap(tree[ls].pl,tree[ls].pr),tree[ls].tag^=1;
	 	 	 swap(tree[rs].pl,tree[rs].pr),tree[rs].tag^=1;
	 	 	 tree[p].tag=0;
		 }
	 }
	 void split(int p,int k,int &x,int &y)
	 {
	 	 if(!p) { x=y=0; return; }
	 	 pushdown(p);
	 	 if(tree[ls].siz<k) x=p,split(rs,k-tree[ls].siz-1,rs,y);
	 	 else y=p,split(ls,k,x,ls);
	 	 pushup(p);
	 }
	 int merge(int x,int y)
	 {
	 	 if(!x || !y) return x|y;
	 	 if(tree[x].rnd<tree[y].rnd)
		 {
		 	 pushdown(x);
		 	 tree[x].pr=merge(tree[x].pr,y);
			 pushup(x);
			 return x;
		 }
		 else
		 {
		 	 pushdown(y);
		 	 tree[y].pl=merge(x,tree[y].pl);
			 pushup(y);
			 return y;
		 }
	 }
 	 int x,y,z,tp;
 	 int sta[Maxn],a[Maxn],tmp[Maxn];
 	 inline int build(int tot)
 	 {
 	 	 tp=0;
		 for(int i=1;i<=tot;i++) a[i]=i;
 	 	 for(int i=1;i<=tot;i++)
 	 	 {
 	 	 	 x=New(a[i]);
 	 	 	 if(tree[x].rnd>tree[sta[tp]].rnd) tree[sta[tp]].pr=x,sta[++tp]=x;
 	 	 	 else
 	 	 	 {
 	 	 	 	 while(tp && tree[sta[tp]].rnd<=tree[x].rnd) tp--;
 	 	 	 	 if(tp) tree[sta[tp]].pr=x;
 	 	 	 	 tree[x].pl=sta[tp+1];
 	 	 	 	 sta[++tp]=x;
			 }
		 }
		 while(tp) pushup(sta[tp--]);
		 return sta[1];
	 }
	 inline void Reverse(int l,int r)
	 {
	 	 split(root,r,x,z),split(x,l-1,x,y);
	 	 swap(tree[y].pl,tree[y].pr),tree[y].tag^=1;
	 	 root=merge(merge(x,y),z);
	 }
	 void print(int p)
	 {
	 	 pushdown(p);
	 	 if(ls) print(ls);
	 	 printf("%lld ",tree[p].val);
	 	 if(rs) print(rs);
	 }
}T2;