第三次做此题。。
不解释啦。
不过变成用SBT来做啦！
SBT好处在于能够保证树的高度为lgn，真真正正的平衡二叉树。
因此删除，插入操作与普通二叉树几乎相同。
#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 SBT
{
int key, size, son[], num;
}T[MAXN]; inline void PushUp(int x)
{
T[x].size=T[T[x].son[]].size+T[T[x].son[]].size+;
} inline int Newnode(int key, int num)
{
++cnt;
T[cnt].num=num;
T[cnt].key=key;
T[cnt].size=;
T[cnt].son[]=T[cnt].son[]=;
return cnt;
} void Rotate(int p, int &x)
{
int y=T[x].son[!p];
T[x].son[!p]=T[y].son[p];
T[y].son[p]=x;
PushUp(x);
PushUp(y);
x=y;
} void Maintain(int &x, int p) //维护SBT的!p子树
{
if(T[T[T[x].son[p]].son[p]].size > T[T[x].son[!p]].size)
Rotate(!p, x);
else if(T[T[T[x].son[p]].son[!p]].size > T[T[x].son[!p]].size)
Rotate(p, T[x].son[p]), Rotate(!p, x);
else return;
Maintain(T[x].son[], );
Maintain(T[x].son[], );
Maintain(x, );
Maintain(x, );
} void Insert(int key, int &x, int num)
{
if(!x) x=Newnode(key, num);
else
{
T[x].size++;
Insert(key, T[x].son[key > T[x].key], num);
Maintain(x, key > T[x].key);
}
} bool Delete(int key, int &x) //删除值为key的节点 key可以不存在
{
if(!x) return ;
if(T[x].key == key)
{
if(!T[x].son[])
{
x=T[x].son[];
return ;
}
if(!T[x].son[])
{
x=T[x].son[];
return ;
}
int y=T[x].son[];
while(T[y].son[])
y=T[y].son[];
T[x].key=T[y].key;
T[x].size--;
return Delete(T[x].key, T[x].son[]);
}
else
if(Delete(key, T[x].son[key > T[x].key]))
{
T[x].size--;
return ;
}
} int GetPth(int p, int &x)
{
if(!x) return ;
if(p == T[T[x].son[]].size+)
return x;
if(p > T[T[x].son[]].size+)
return GetPth(p-T[T[x].son[]].size-, T[x].son[]);
else
return GetPth(p, T[x].son[]);
} int main ()
{
int p, key, num, x;
while(scanf("%d", &p) && p)
{
switch (p)
{
case :
scanf("%d%d", &num, &key);
Insert(key, rt, num);
break;
case :
x=GetPth(T[rt].size, rt);
if(x)
{
printf("%d\n",T[x].num);
Delete(T[x].key, rt);
}
else
printf("0\n");
break;
case :
x=GetPth(, rt);
if(x)
{
printf("%d\n",T[x].num);
Delete(T[x].key, rt);
}
else
printf("0\n");
}
}
return ;
}