POJ 3481 Double Queue

平衡树。。

熟悉些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
", 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
", key[res]); del(val[res]), cnt --;
        }
    }
    return 0;
}