★★☆ 输入文件：arr.in 输出文件：arr.out 简单对比
时间限制：1 s 内存限制：3 MB
Source: SDOI2007 Day2
【问题描述】
一般的数组大家都经常使用，相信很多同学没有见过下面的超级数组。
超级数组存储的是一些正整数，它还支持下面的两个操作
(1)、插入一个元素，命令是 "i key" 。 key 是要插入的数。
(2)、输出第 k 大元素并删除该元素，命令是 "d k"。输出第 k 大元素并删除它。
“第 k 大”是指：现有的数中，如果从小到大排好序，从最小的开始作为第一大算起，
一直数到第 k 个。
现在给出一个开始是空的超级数组，请维护好该数组。
【输入】(arr.in)
第一行 n、m：n<=1 000 000 000 , m<=100 000。表示插入数的范围是 1 至n ,共有m 条命令（包括插入和删除）。
以下 m 行，每行一条命令，如题中描述。每条命令中字母和后面的数字之间一个空格。
保证输入数据是正确的，删除的数一定存在。
【输出】（arr.out）
对于每个删除命令，按删除命令顺序输出删除的数，每个数一行
【样例输入】
100 10
i 57
i 99
i 65
d 3
i 89
d 2
d 2
d 1
i 93
i 29
【样例输出】
99
65
89
57
SBT模板题。。。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int maxn=;
int key[maxn],siz[maxn],lc[maxn],rc[maxn];
int root,tot;
int N,M;
char s[];
void r_rotate(int &rt){
int k=lc[rt];
lc[rt]=rc[k];
rc[k]=rt;
siz[k]=siz[rt];
siz[rt]=siz[lc[rt]]+siz[rc[rt]]+;
rt=k;
}
void l_rotate(int &rt){
int k=rc[rt];
rc[rt]=lc[k];
lc[k]=rt;
siz[k]=siz[rt];
siz[rt]=siz[lc[rt]]+siz[rc[rt]]+;
rt=k;
}
void Maintain(int &rt,bool flag){
if(flag==false){
if(siz[lc[lc[rt]]]>siz[rc[rt]]) r_rotate(rt);
else if(siz[rc[lc[rt]]]>siz[rc[rt]]){
l_rotate(lc[rt]);
r_rotate(rt);
}
else return ;
}
else{
if(siz[rc[rc[rt]]]>siz[lc[rt]]) l_rotate(rt);
else if(siz[lc[rc[rt]]]>siz[lc[rt]]){
r_rotate(rc[rt]);
l_rotate(rt);
}
else return ;
}
Maintain(lc[rt],false); Maintain(rc[rt],true);
Maintain(rt,false); Maintain(rt,true);
}
void insert(int &rt,int v){
if(rt==){
rt=++tot;
key[rt]=v;
siz[rt]=; lc[rt]=rc[rt]=;
return ;
}
siz[rt]++;
if(v<=key[rt]) insert(lc[rt],v);
else insert(rc[rt],v);
Maintain(rt,false); Maintain(rt,true);
}
int Delete(int &rt,int v){
int ans;
siz[rt]--;
if(v==key[rt]||(v<key[rt]&&lc[rt]==)||(v>key[rt]&&rc[rt]==)){
ans=key[rt];
if(lc[rt]==||rc[rt]==) rt=lc[rt]+rc[rt];
else key[rt]=Delete(lc[rt],key[rt]+);
return ans;
}
if(v<key[rt]) ans=Delete(lc[rt],v);
else ans=Delete(rc[rt],v);
return ans;
}
bool find(int &rt,int v){
if(rt==) return false;
if(v==key[rt]) return true;
if(v<key[rt]) return find(lc[rt],v);
if(v>key[rt]) return find(rc[rt],v);
}
int select(int &rt,int v){
if(v==siz[lc[rt]]+) return key[rt];
else if(v<siz[lc[rt]]+) return select(lc[rt],v);
else return select(rc[rt],v-siz[lc[rt]]-);
}
int main(){
freopen("arr.in","r",stdin);
freopen("arr.out","w",stdout);
scanf("%d%d",&N,&M);
for(int i=,tmp;i<=M;i++){
scanf("%s%d",s,&tmp);
if(s[]=='i') insert(root,tmp);
else{
int ans=select(root,tmp);
printf("%d\n",ans);
Delete(root,ans);
}
}
return ;
}