题目链接
题意分析
明眼人一看就会发现这是一道裸的Splay吧准确来说是平衡树可是本蒟蒻就会使用Splay
对于五种操作 转换成Splay就是
1.把指定元素放在序列首位
我们让该元素成为root 然后将ta的左子树合并到该元素的后继
2.把指定元素放在序列末尾
我们让该元素成为root 然后将ta的右子树合并到该元素的前驱
3.把该元素向上/下移动一位
将该元素同其前驱/后继交换
4.查询元素k的排名
5.查询排名为k的元素
不过由于这里的元素存在编号 而且编号不是Splay中用于排序的权值
所以 这里的Splay需要使用插入顺序以及后面的调整作为排序的依据
同时使用一个数组 pos[x] 表示编号为x的元素对应在Splay的位置
CODE:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#define M 1008611
using namespace std;
int n,m,cnt,root;
int pos[M];
struct Tree
{
int son[2],fa,siz,val;
}tre[M];
int getd(int x)
{return tre[tre[x].fa].son[1]==x;}
void pushup(int x)
{
tre[x].siz=tre[tre[x].son[0]].siz+tre[tre[x].son[1]].siz+1;
pos[tre[tre[x].son[0]].val]=tre[x].son[0];
pos[tre[tre[x].son[1]].val]=tre[x].son[1];
pos[tre[x].val]=x;//时刻要注意更新编号
}
void rotate(int x)
{
int fat=tre[x].fa,fatt=tre[tre[x].fa].fa;
int d1=getd(x),d2=getd(fat);
tre[fat].son[d1]=tre[x].son[d1^1];tre[tre[x].son[d1^1]].fa=fat;
tre[fatt].son[d2]=x;tre[x].fa=fatt;
tre[x].son[d1^1]=fat;tre[fat].fa=x;
pushup(fat);pushup(x);
}
void Splay(int x,int goal)
{
while(tre[x].fa!=goal)
{
int fat=tre[x].fa,fatt=tre[tre[x].fa].fa;
int d1=getd(x),d2=getd(fat);
if(fatt!=goal)
{
if(d1==d2) rotate(fat);
else rotate(x);
}
rotate(x);
}
if(goal==0) root=x;
}
void insert(int x)
{
tre[++cnt].val=x;tre[cnt].siz=1;
pos[x]=cnt;tre[cnt].son[0]=tre[cnt].son[1]=0;
if(cnt>1)
{
tre[cnt-1].son[1]=cnt;
tre[cnt].fa=cnt-1;
Splay(cnt,0);
}
}
void Top(int x)
{
x=pos[x];Splay(x,0);
if(!tre[x].son[0]) return;
else if(!tre[x].son[1]) tre[x].son[1]=tre[x].son[0],tre[x].son[0]=0;
else
{
int now=tre[x].son[1];
while(tre[now].son[0]) now=tre[now].son[0];
tre[tre[x].son[0]].fa=now;
tre[now].son[0]=tre[x].son[0];
tre[x].son[0]=0;
Splay(now,0);
}
}
void Bottom(int x)
{
x=pos[x];Splay(x,0);
if(!tre[x].son[1]) return;
else if(!tre[x].son[0]) tre[x].son[0]=tre[x].son[1],tre[x].son[1]=0;
else
{
int now=tre[x].son[0];
while(tre[now].son[1]) now=tre[now].son[1];
tre[tre[x].son[1]].fa=now;
tre[now].son[1]=tre[x].son[1];
tre[x].son[1]=0;
Splay(now,0);
}
}
void Change(int x,int y)
{
if(y==0) return;
x=pos[x];
Splay(x,0);
if(y==1)
{
if(!tre[x].son[1]) return;
else
{
int now=tre[x].son[1];
while(tre[now].son[0]) now=tre[now].son[0];
pos[tre[x].val]=now;pos[tre[now].val]=x;
swap(tre[x].val,tre[now].val);
}
}
else
{
if(!tre[x].son[0]) return;
else
{
int now=tre[x].son[0];
while(tre[now].son[1]) now=tre[now].son[1];
pos[tre[x].val]=now;pos[tre[now].val]=x;
swap(tre[x].val,tre[now].val);
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1,x;i<=n;++i)
{
scanf("%d",&x);
insert(x);
}
while(m--)
{
char s[10];int x,y;
scanf("%s",s);
if(s[0]=='T')
{
scanf("%d",&x);
Top(x);
}
if(s[0]=='B')
{
scanf("%d",&x);
Bottom(x);
}
if(s[0]=='I')
{
scanf("%d%d",&x,&y);
Change(x,y);
}
if(s[0]=='A')
{
scanf("%d",&x);
x=pos[x];
Splay(x,0);
printf("%d\n",tre[tre[x].son[0]].siz);
}
if(s[0]=='Q')
{
scanf("%d",&x);
int now=root;
while(1)
{
if(tre[tre[now].son[0]].siz>=x) now=tre[now].son[0];
else if(tre[tre[now].son[0]].siz+1<x)
{
x-=tre[tre[now].son[0]].siz+1;
now=tre[now].son[1];
}
else break;
}
printf("%d\n",tre[now].val);
}
}
return 0;
}