需要这样一个数据结构，支持如下操作

1：插入优先级为p，编号为k的节点

2：查询优先级最高的节点，输出编号并删除

3：查询优先级最低的节点，输出编号并删除

用一颗SBT即可完美解决问题，没什么好说的，多说无益~~~

1 program pku3481(input,output);  2 var  3     left,right,key,s,th:array[0..200000] of longint;  4     tot,root:longint;  5 procedure left_rotate(var t:longint);  6 var  7     k:longint;  8 begin  9     k:=right[t]; 10     right[t]:=left[k]; 11     left[k]:=t; 12     s[k]:=s[t]; 13     s[t]:=s[left[t]]+s[right[t]]+1; 14     t:=k; 15 end;{
      left_rotate } 16 procedure right_rotate(var t:longint); 17 var 18     k:longint; 19 begin 20     k:=left[t]; 21     left[t]:=right[k]; 22     right[k]:=t; 23     s[k]:=s[t]; 24     s[t]:=s[left[t]]+s[right[t]]+1; 25     t:=k; 26 end;{
      right_rotate } 27 procedure maintain(var t:longint;flag:boolean); 28 begin 29     if not flag then 30     begin 31         if s[left[left[t]]]>s[right[t]] then 32             right_rotate(t) 33         else 34             if s[right[left[t]]]>s[right[t]] then 35             begin 36                 left_rotate(left[t]); 37                 right_rotate(t); 38             end 39             else 40                 exit; 41     end 42     else 43     begin 44         if s[right[right[t]]]>s[left[t]] then 45             left_rotate(t) 46         else 47             if s[left[right[t]]]>s[left[t]] then 48             begin 49                 right_rotate(right[t]); 50                 left_rotate(t); 51             end 52             else 53                 exit; 54     end; 55     maintain(left[t],false); 56     maintain(right[t],true); 57     maintain(t,false); 58     maintain(t,true); 59 end;{
      maintain } 60 procedure insert(var now,k,u:longint); 61 begin 62     if now=0 then 63     begin 64         inc(tot); 65         now:=tot; 66         s[now]:=1; 67         left[now]:=0; 68         right[now]:=0; 69         key[now]:=k; 70         th[now]:=u; 71     end 72     else 73     begin 74         inc(s[now]); 75         if k
      
       =key[now]); 80     end; 81 end;{
      insert } 82 function delete(var t:longint;k:longint):longint; 83 begin 84     dec(s[t]); 85     if (k=key[t])or((k
       
        key[t])and(right[t]=0)) then 86     begin 87         delete:=key[t]; 88         if left[t]*right[t]=0 then 89             t:=left[t]+right[t] 90         else 91             key[t]:=delete(left[t],k+1); 92     end 93     else 94         if k
        
         0 do123     begin124         if x=1 then125         begin126             readln(y,z);127             insert(root,z,y);128         end;129         if x=2 then130             if s[root]=0 then131                 writeln(0)132             else133             begin134                 y:=get_max_number(root);135                 writeln(th[y]);136                 delete(root,key[y]);137             end;138         if x=3 then139             if s[root]=0 then140                 writeln(0)141             else142             begin143                 y:=get_min_number(root);144                 writeln(th[y]);145                 delete(root,key[y]);146             end;147         read(x);148     end;149 end;{
      main }150 begin151     main;152 end.