最后撸一发splay。
之前用treap撸的，现在splay也找到感觉了，果然不同凡响，两者之间差别与精妙之处各有其精髓！
真心赞一个！
POJ平衡树的题目还是比较少，只能挑之前做过的捏一捏。但是收获很多，这一天做的题都是有一定普遍性的。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <utility>
#include <vector>
#include <queue>
#include <map>
#include <set>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
#define INF 0x3f3f3f3f
#define MAXN 100005 using namespace std; int cnt=, rt=; struct Tree
{
int key, size, fa, son[], num;
void set(int _key, int _size, int _fa, int _num)
{
key=_key;
size=_size;
fa=_fa;
son[]=son[]=;
num=_num;
}
}T[MAXN]; inline void PushUp(int x)
{
T[x].size=T[T[x].son[]].size+T[T[x].son[]].size+;
} inline void Rotate(int x, int p) //0左旋 1右旋
{
int y=T[x].fa;
T[y].son[!p]=T[x].son[p];
T[T[x].son[p]].fa=y;
T[x].fa=T[y].fa;
if(T[x].fa)
T[T[x].fa].son[T[T[x].fa].son[] == y]=x;
T[x].son[p]=y;
T[y].fa=x;
PushUp(y);
PushUp(x);
} void Splay(int x, int To) //将x节点插入到To的子节点中
{
while(T[x].fa != To)
{
if(T[T[x].fa].fa == To)
Rotate(x, T[T[x].fa].son[] == x);
else
{
int y=T[x].fa, z=T[y].fa;
int p=(T[z].son[] == y);
if(T[y].son[p] == x)
Rotate(x, !p), Rotate(x, p); //之字旋
else
Rotate(y, p), Rotate(x, p); //一字旋
}
}
if(To == ) rt=x;
} int find(int key) //返回值为key的节点 若无返回0 若有将其转移到根处
{
int x=rt;
while(x && T[x].key != key)
x=T[x].son[key > T[x].key];
if(x) Splay(x, );
return x;
} int prev() //返回比根值小的最大值 若无返回0 若有将其转移到根处
{
int x=T[rt].son[];
if(!x) return ;
while(T[x].son[])
x=T[x].son[];
Splay(x, );
return x;
} int succ() //返回比根值大的最小值 若无返回0 若有将其转移到根处
{
int x=T[rt].son[];
if(!x) return ;
while(T[x].son[])
x=T[x].son[];
Splay(x, );
return x;
} void Insert(int key, int num) //插入key 并且将该节点转移到根处
{
if(!rt)
T[rt = cnt++].set(key, , , num);
else
{
int x=rt, y=;
while(x)
{
y=x;
x=T[x].son[key > T[x].key];
}
T[x = cnt++].set(key, , y, num);
T[y].son[key > T[y].key]=x;
Splay(x, );
}
} void Delete(int key) //删除值为key的节点 若有重点只删其中一个 x的前驱移动到根处
{
int x=find(key);
if(!x) return;
int y=T[x].son[];
while(T[y].son[])
y=T[y].son[];
int z=T[x].son[];
while(T[z].son[])
z=T[z].son[];
if(!y && !z)
{
rt=;
return;
}
if(!y)
{
Splay(z, );
T[z].son[]=;
PushUp(z);
return;
}
if(!z)
{
Splay(y, );
T[y].son[]=;
PushUp(y);
return;
}
Splay(y, );
Splay(z, y);
T[z].son[]=;
PushUp(z);
PushUp(y);
} int GetPth(int p) //获得第p小的节点 并将其转移到根处
{
if(!rt) return ;
int x=rt, ret=;
while(x)
{
if(p == T[T[x].son[]].size+)
break;
if(p>T[T[x].son[]].size+)
{
p-=T[T[x].son[]].size+;
x=T[x].son[];
}
else
x=T[x].son[];
}
Splay(x, );
return x;
} int main ()
{
int p, key, num, x;
while(scanf("%d", &p) && p)
{
switch (p)
{
case :
scanf("%d%d", &num, &key);
Insert(key, num);
break;
case :
x=GetPth(T[rt].size);
if(x)
{
printf("%d\n",T[x].num);
Delete(T[x].key);
}
else
printf("0\n");
break;
case :
x=GetPth();
if(x)
{
printf("%d\n",T[x].num);
Delete(T[x].key);
}
else
printf("0\n");
}
}
return ;
}
之后必须写一篇Splay ， Treap ， SBT（未学）的总结与模板。
敬请期待！