题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4006
题目大意:
给定n个操作，操作分两种，插入和查询第k大的数。n<=1000000
解题思路：因为本题没有删除操作，所以变得特别简单，只需要维护一个大小为k的小顶堆即可。
但是如果有删除操作，就变地复杂了，所以用SBT写了这道题，怒写2遍，明天晚上黄金十点半再写三遍，测模版的没什么好说的。
测试数据:
8 3
I 1
I 2
I 3
Q
I 5
Q
I 4
Q
C艹代码:
#include <stdio.h>
#include <string.h>
#define MAX 1000010
int n,m;
struct SBT {
int left,right,size,key;
void Init() {
left = right = 0;
size = 1;
}
}a[MAX];
int tot,root;
void left_rotate(int &t) {
int k = a[t].right;
a[t].right = a[k].left;
a[k].left = t;
a[k].size = a[t].size;
a[t].size = a[a[t].left].size + a[a[t].right].size + 1;
t = k;
}
void right_rotate(int &t) {
int k = a[t].left;
a[t].left = a[k].right;
a[k].right = t;
a[k].size = a[t].size;
a[t].size = a[a[t].left].size + a[a[t].right].size + 1;
t = k;
}
void maintain(int &t,int flag) {
if (flag == 0) {
if (a[a[a[t].left].left].size > a[a[t].right].size)
right_rotate(t);
else if (a[a[a[t].left].right].size > a[a[t].right].size)
left_rotate(a[t].left),right_rotate(t);
else return;
}
else {
if (a[a[a[t].right].right].size > a[a[t].left].size)
left_rotate(t);
else if (a[a[a[t].right].left].size > a[a[t].left].size)
right_rotate(a[t].right),left_rotate(t);
else return;
}
maintain(a[t].left,0);
maintain(a[t].right,1);
maintain(t,0);
maintain(t,1);
}
void insert(int &t,int v) {
if (t == 0)
t = ++tot,a[t].Init(),a[t].key = v;
else {
a[t].size++;
if (v < a[t].key)
insert(a[t].left,v);
else insert(a[t].right,v);
maintain(t,v>=a[t].key);
}
}
int del(int &t,int v) {
if (!t) return 0;
a[t].size--;
if (v == a[t].key || v < a[t].key && !a[t].left
|| v > a[t].key && !a[t].right) {
if (a[t].left && a[t].right) {
int p = del(a[t].left,v+1);
a[t].key = a[p].key;
return p;
}
else {
int p = t;
t = a[t].left + a[t].right;
return p;
}
}
else return del(v<a[t].key?a[t].left:a[t].right,v);
}
int find(int t,int k) {
if (k <= a[a[t].left].size)
return find(a[t].left,k);
if (k > a[a[t].left].size + 1)
return find(a[t].right,k-a[a[t].left].size-1);
return a[t].key;
}
int main()
{
int i,j,k;
while (scanf("%d%d",&n,&m) != EOF) {
tot = root = 0;
char ope[10];
while (n--) {
scanf("%s",ope);
if (ope[0] == 'I') {
scanf("%d",&k);
insert(root,k);
}
else printf("%d\n",find(root,a[root].size+1-m));
}
}
}
本文ZeroClock原创，但可以转载，因为我们是兄弟。