POJ 3481 SBT基础题
题意：1表示插入客户K，他的优先级是P（相当于大小），2表示输出当前优先级最高的客户（即找出最大值），并且删除。3同理输出最低级的。
思路：运用SBT里面的get_min(),get_max()操作可以轻松完成。具体见代码
[cpp]
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 100005
#define inf 1<<28
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define FOR(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
using namespace std;
struct SBT
{
int left, right ,num , size , priority;
}tree[Max];
void left_rot(int &x)//左旋
{
int y = tree[x].right;
tree[x].right = tree[y].left;
tree[y].left = x;
tree[y].size = tree[x].size;
tree[x].size = tree[tree[x].left].size + tree[tree[x].right].size + 1;
x = y;
}
void right_rot(int &x)//右旋
{
int y = tree[x].left;
tree[x].left = tree[y].right;
tree[y].right = x;
tree[y].size = tree[x].size;
tree[x].size = tree[tree[x].left].size + tree[tree[x].right].size + 1;
x = y;
}
void maintain(int &x,bool flag)//更新
{
if(!flag)//左子树是0
{
if(tree[tree[tree[x].left].left].size > tree[tree[x].right].size)
right_rot(x);
else if(tree[tree[tree[x].left].right].size > tree[tree[x].right].size)
{
left_rot(tree[x].left);
right_rot(x);
}
else return ;
}
else//右子树是1
{
if(tree[tree[tree[x].right].right].size > tree[tree[x].left].size)
left_rot(x);
else if(tree[tree[tree[x].right].left].size > tree[tree[x].left].size)
{
right_rot(tree[x].right);
left_rot(x);
}
else return ;
}
maintain(tree[x].left,0);
maintain(tree[x].right,1);
maintain(x,1);
maintain(x,0);
}
int root , top;
void insert(int &x ,int num ,int priority)//插入这里，p是优先级，也就是一般SBT里面存的大小，而那个num可以理解为客户的名字，输出用的而已。
{
if (x == 0)
{
x = ++top;
tree[x].size = 1;
tree[x].left = tree[x].right = 0;
tree[x].num = num ;
tree[x].priority = priority;
}
else
{
tree[x].size ++;
if(priority < tree[x].priority)insert(tree[x].left , num , priority);
else insert(tree[x].right , num ,priority);
maintain(root , priority >= tree[x].priority);
}
}
int del(int &x ,int priority)
{
int d_priority ;
if(!x)return 0;
tree[x].size --;
if(priority == tree[x].priority || (tree[x].priority >priority && tree[x].left == 0)||(tree[x].priority < priority && tree[x].right == 0))
{
d_priority = tree[x].priority;
if(tree[x].left && tree[x].right )
{
tree[x].priority = del(tree[x].left , tree[x].priority + 1);
}
else
x = tree[x].left + tree[x].right ;
}
else if(priority > tree[x].priority)
d_priority = del(tree[x].right, priority );
else if (priority < tree[x].priority)
d_priority = del(tree[x].left , priority);
return d_priority;
}
int get_min()
{
int x;
for (x = root ; tree[x].left; x = tree[x].left );
printf("%d\n",tree[x].num);
return tree[x].priority;//返回这个值，用于删除
}
int get_max()
{
int x ;
for (x = root ; tree[x].right ; x = tree[x].right );
printf("%d\n",tree[x].num);
return tree[x].priority;//同理
}
int main()
{
int n ;
root = top = 0;
while(scanf("%d",&n)&& n )
{
if( n == 1)
{
int a , b ;
scanf("%d%d",&a,&b);
insert(root , a, b);
}
