Book 书架 bzoj-1861 Zjoi-2006
题目大意：给你一个序列，支持：将指定编号的元素抽出，放到序列顶（底）；将指定编号元素左右篡位；查询指定编号元素位置；查询指定数量位置元素编号。
注释：$1\le n,m\le 8\cdot 10^4$
想法：非旋转Treap裸题
需要注意的就是那个反复横跳的操作，只需要把指定元素和它接下来要交换的元素都split出来，然后一一合并即可。
最后，附上丑陋的代码... ...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 80010
#define mp make_pair
using namespace std;
typedef pair<int,int> par;
int n,m,root;
int ls[N],rs[N],size[N],key[N],fa[N];
inline void pushup(int x)
{
size[x]=size[ls[x]]+size[rs[x]]+1;
}
int merge(int x,int y)
{
if(!x||!y) return x|y;
if(key[x]>key[y])
{
rs[x]=merge(rs[x],y);fa[rs[x]]=x;
pushup(x); return x;
}
ls[y]=merge(x,ls[y]);fa[ls[y]]=y;
pushup(y); return y;
}
par split(int x,int k)
{
if(!k) return mp(0,x);
int lson=ls[x],rson=rs[x];
if(k==size[lson])
{
ls[x]=0;pushup(x);
fa[lson]=0;
return mp(lson,x);
}
if(k==size[lson]+1)
{
rs[x]=0;pushup(x);
fa[rson]=0;
return mp(x,rson);
}
if(k<size[lson])
{
par t=split(lson,k);
ls[x]=t.second;fa[ls[x]]=x;pushup(x);
return mp(t.first,x);
}
par t=split(rson,k-size[ls[x]]-1);
rs[x]=t.first;fa[rs[x]]=x;pushup(x);
return mp(x,t.second);
}
int getid(int x)
{
int flag=1,t=x,ans=0;
while(t)
{
if(flag)ans+=size[ls[t]]+1;
flag=(t==rs[fa[t]]);
t=fa[t];
}
return ans-1;
}
int find(int x)
{
x--;int t=root;
while(1)
{
if(x==size[ls[t]]) return t;
if(x<size[ls[t]]) t=ls[t];
else x-=size[ls[t]]+1,t=rs[t];
}
}
int main()
{
cin >> n >> m ;
for(int x,i=1;i<=n;i++)
{
scanf("%d",&x);
size[x]=1,key[x]=rand()*rand();
root=merge(root,x);
}
char flag[10];
for(int x,y,i=1;i<=m;i++)
{
scanf("%s",flag);
if(flag[0]=='T')
{
scanf("%d",&x);
int id=getid(x);
par t2=split(root,id+1),t1=split(t2.first,id);
root=merge(t1.second,merge(t1.first,t2.second));
}
else if(flag[0]=='B')
{
scanf("%d",&x);
int id=getid(x);
par t2=split(root,id+1),t1=split(t2.first,id);
root=merge(merge(t1.first,t2.second),t1.second);
}
else if(flag[0]=='I')
{
scanf("%d%d",&x,&y);
if(!y)continue;
if(y==-1)
{
int id=getid(x);
par t3=split(root,id+1),t2=split(t3.first,id),t1=split(t2.first,id-1);
root=merge(merge(merge(t1.first,t2.second),t1.second),t3.second);
}
else
{
int id=getid(x);
par t3=split(root,id+2),t2=split(t3.first,id+1),t1=split(t2.first,id);
root=merge(merge(merge(t1.first,t2.second),t1.second),t3.second);
}
}
else if(flag[0]=='A')
{
scanf("%d",&x);
printf("%d\n",getid(x));
}
else
{
scanf("%d",&x);
printf("%d\n",find(x));
}
}
return 0;
}
小结：非旋转Treap就是比splay优（傲娇脸）