路漫漫其修远兮~
手抄一枚splay树 长长的模版。。
关于spaly树的讲解 网上很多随手贴一篇 貌似这题可以用什么bst啦 堆啦 平衡树啦 等等 这些本质都是有共同点的 查找、删除特别快 因为都有序 而且平衡~
看题很容易想到用线段树做 不过数太大了 离散化嘛 你肯定这么想 不过这题真不好离散 没想出来 只能硬啃这树那树了
用splay树存下被删除的数 为原先的第几 再根据左边有多少个节点 右边有多少个节点 与询问的数比较大小 看他具体该在哪个位置
每插入一个数 就把它旋到根节点 这样会节省时间 应该跟输入数据有关 我试了把询问时的那步旋转去掉 跑得死慢了
看代码吧 挺有意思的
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#define N 10010
using namespace std;
int n,m;
struct splaytree
{
int size[N],ch[N][],f[N],va[N];
int root,top;
inline void zig(int x)
{
int y = f[x],z = f[y];
ch[y][] = ch[x][];f[ch[x][]] = y;
f[x] = z;ch[x][] = y;f[y] = x;
if(z) ch[z][ch[z][]==y] = x;
pushup(y);
}
inline void zag(int x)
{
int y = f[x],z = f[y];
ch[y][] = ch[x][];f[ch[x][]] = y;
ch[x][] = y;f[y] = x;f[x] = z;
if(z) ch[z][ch[z][]==y] = x;
pushup(y);
}
inline void zigzig(int x)
{
int y = f[x],z = f[y],fz = f[z];
ch[z][] = ch[y][]; f[ch[y][]] = z;
ch[y][] = ch[x][]; f[ch[x][]] = y;
f[z] = y;ch[y][] = z;
f[y] = x;ch[x][] = y;
f[x] = fz;
if(fz) ch[fz][ch[fz][]==z] = x;
pushup(z);pushup(y);
}
inline void zagzag(int x){ int y=f[x], z=f[y], fz=f[z]; ch[z][]=ch[y][]; f[ch[y][]]=z; ch[y][]=ch[x][]; f[ch[x][]]=y; f[z] = y;ch[y][] = z;
f[y] = x;ch[x][] = y;
f[x] = fz;
if(fz) ch[fz][ch[fz][]==z] = x;
pushup(z);pushup(y);
}
inline void zigzag(int x)
{
int y = f[x],z = f[y],fz = f[z];
ch[y][] = ch[x][] ; f[ch[x][]] = y;
ch[z][] = ch[x][] ; f[ch[x][]] = z;
f[z] = x;ch[x][] = y;
f[y] = x;ch[x][] = z;
f[x] = fz;
if(fz) ch[fz][ch[fz][]==z] = x;
pushup(y);pushup(z);
}
inline void zagzig(int x)
{
int y = f[x],z = f[y],fz = f[z];
ch[y][] = ch[x][] ; f[ch[x][]] = y;
ch[z][] = ch[x][] ; f[ch[x][]] = z;
f[z] = x;ch[x][] = z;
f[y] = x;ch[x][] = y;
f[x] = fz;
if(fz) ch[fz][ch[fz][]==z] = x;
pushup(y);pushup(z);
}
void splay(int x,int goal)
{
int y,z;
while(f[x]!=goal)
{
if(f[f[x]]==goal)
{
y = f[x];
if(ch[y][]==x)
zig(x);
else
zag(x);
}
else
{
y = f[x];z =f[y];
if(ch[z][]==y)
{
if(ch[y][]==x)
zigzig(x);
else
zagzig(x);
}
else
{
if(ch[y][]==x)
zagzag(x);
else
zigzag(x);
}
}
}
pushup(x);
if(f[x]==)
root = x;
}
inline void pushup(int x)
{
size[x] = size[ch[x][]]+size[ch[x][]]+;
}
void init()
{
size[] = ch[][] = ch[][] = f[] = root = va[] = top = ;
insert();
}
inline int newnode(int v)
{
size[++top] = ;
ch[top][] = ch[top][] = f[top] = ;
va[top] = v;
return top;
}
void insert(int v)
{
int r = root,x;
for(;;)
{
if(v>=va[r])
{
if(ch[r][])
r = ch[r][];
else
{
x = newnode(v);
ch[r][] = x;
f[x] = r;
break;
}
}
else
{
if(ch[r][])
r = ch[r][];
else
{
x = newnode(v);
ch[r][] = x;
f[x] = r;
break;
}
}
}
splay(x,);
}
int query(int v)
{
int r = root,k = v,res = size[ch[root][]];
for(;;)
{
if(k<va[r]-res)
{
if(ch[r][])
{
r = ch[r][];
res -= size[ch[r][]]+;
}
else
{
splay(r,);
return k+res;
}
}
else
{
if(ch[r][])
{
r = ch[r][];
res += +size[ch[r][]];
}
else
{
splay(r,);
return k+res+;
}
}
}
}
}tree;
int main()
{
int k;
char s[];
tree.init();
scanf("%d%d",&n,&m);
while(m--)
{
scanf("%s%d",s,&k);
if(s[]=='L')
printf("%d\n",tree.query(k));
else
{
int x = tree.query(k);
tree.insert(x);
}
}
return ;
}