题目大意: 给定n个操作，操作分两种，插入和查询第k大的数。n<=1000000
解题思路：因为本题没有删除操作，所以变得特别简单，只需要维护一个大小为k的小顶堆即可。
但是如果有删除操作，就变地复杂了，所以用SBT写了这道题，怒写2遍，明天晚上黄金十点半再写三遍，测模版的没什么好说的。
测试数据:
8 3
I 1
I 2
I 3
Q
I 5
Q
I 4
Q
C艹代码:
[cpp]
#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);
}