平衡树。。
熟悉些fhq-Treap，为啥我在poj读入优化不能用啊
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <cstring>
#define INF 0x3f3f3f3f
#define full(a, b) memset(a, b, sizeof a)
using namespace std;
typedef long long ll;
inline int lowbit(int x){ return x & (-x); }
inline int read(){
int X = 0, w = 0; char ch = 0;
while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }
while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
return w ? -X : X;
}
inline int gcd(int a, int b){ return a % b ? gcd(b, a % b) : b; }
inline int lcm(int a, int b){ return a / gcd(a, b) * b; }
template<typename T>
inline T max(T x, T y, T z){ return max(max(x, y), z); }
template<typename T>
inline T min(T x, T y, T z){ return min(min(x, y), z); }
template<typename A, typename B, typename C>
inline A fpow(A x, B p, C lyd){
A ans = 1;
for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;
return ans;
}
const int N = 1000005;
int tree[N][2], key[N], val[N], rnd[N], size[N], tot, root;
int tx, ty, tz, cnt;
int rndom(){
return rand() << 15 | rand();
}
int newNode(int k, int p){
key[++tot] = k, val[tot] = p, rnd[tot] = rndom(), size[tot] = 1;
return tot;
}
void push_up(int x){
size[x] = size[tree[x][0]] + size[tree[x][1]] + 1;
}
int merge(int x, int y){
if(!x || !y) return x + y;
if(rnd[x] < rnd[y]){
tree[x][1] = merge(tree[x][1], y);
push_up(x);
return x;
}
else{
tree[y][0] = merge(x, tree[y][0]);
push_up(y);
return y;
}
}
void split(int cur, int k, int &x, int &y){
if(!cur) { x = 0, y = 0; return; }
if(val[cur] <= k) x = cur, split(tree[cur][1], k, tree[cur][1], y);
else y = cur, split(tree[cur][0], k, x, tree[cur][0]);
push_up(cur);
}
void insert(int k, int p){
split(root, p, tx, ty);
root = merge(merge(tx, newNode(k, p)), ty);
}
void del(int p){
split(root, p, tx, tz);
split(tx, p - 1, tx, ty);
ty = merge(tree[ty][0], tree[ty][1]);
root = merge(merge(tx, ty), tz);
}
int minimum(){
int cur = root;
while(tree[cur][0] != 0) cur = tree[cur][0];
return cur;
}
int maximum(){
int cur = root;
while(tree[cur][1] != 0) cur = tree[cur][1];
return cur;
}
int select(int cur, int k){
while(1){
if(size[tree[cur][0]] >= k) cur = tree[cur][0];
else{
if(size[tree[cur][0]] + 1 == k) return cur;
k = k - size[tree[cur][0]] - 1, cur = tree[cur][1];
}
}
}
void init(){
full(tree, 0), full(val, 0), full(size, 0);
full(key, 0), full(rnd, 0);
cnt = tot = root = 0;
}
int main(){
srand(time(0));
int opt; init();
while(scanf("%d", &opt) != EOF && opt){
if(opt == 1) {
int k, p; scanf("%d%d", &k, &p);
insert(k, p), cnt ++;
}
else if(opt == 2){
if(cnt == 0){
puts("0");
continue;
}
int res = maximum();
//int res = select(root, size[root]);
printf("%d\n", key[res]); del(val[res]), cnt --;
}
else if(opt == 3){
if(cnt == 0){
puts("0");
continue;
}
int res = minimum();
//int res = select(root, 1);
printf("%d\n", key[res]); del(val[res]), cnt --;
}
}
return 0;
}