POJ - 3481 - 平衡树模板题2

跟 BZOJ 3224 不同的是
优先级是题目中给定的，且不同
所以把 sz 域删掉就好

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
int n, cnt, rt;
int maxval, minval;

struct node{
    int lc, rc;
    int val, pri;
    int num;
}tr[maxn];

int NewNode(int v, int num){
    tr[++cnt].val = v;
    tr[cnt].pri = rand();
    tr[cnt].num = num;
    tr[cnt].lc = tr[cnt].rc = 0;
    return cnt;
}

void Zig(int &p){
    //Right Rotate
    int q = tr[p].lc;
    tr[p].lc = tr[q].rc;
    tr[q].rc = p;
    p = q;
}

void Zag(int &p){
    int q = tr[p].rc;
    tr[p].rc = tr[q].lc;
    tr[q].lc = p;
    p = q;
}

void Insert(int &p, int v, int num){
    if (!p){
        p = NewNode(v, num);
        return;
    }
    if (v <= tr[p].val){
        Insert(tr[p].lc, v, num);
        if (tr[p].pri < tr[tr[p].lc].pri)
            Zig(p);
    }
    else{
        //v > tr[p].val
        Insert(tr[p].rc, v, num);
        if (tr[p].pri < tr[tr[p].rc].pri)
            Zag(p);
    }
}

void Delete(int &p, int v){
    if (!p) return;
    if (v == tr[p].val){
        if (!tr[p].lc || !tr[p].rc)
            p = tr[p].lc + tr[p].rc;
        else if (tr[tr[p].lc].pri > tr[tr[p].rc].pri){
            Zig(p);
            Delete(tr[p].rc, v);
            }
        else{
            Zag(p);
            Delete(tr[p].lc, v);
        }
        return;
    }
    if (v < tr[p].val)
        Delete(tr[p].lc, v);
    else
        Delete(tr[p].rc, v);
}

int GetPre(int v){
    int p = rt;
    int res = 0;
    while(p){
        if (tr[p].val < v){
            res = tr[p].val;
            p = tr[p].rc;
        }
        else
            p = tr[p].lc;
    }
    return res;
}

int GetNxt(int v){
    int p = rt;
    int res = 0;
    while(p){
        if (tr[p].val > v){
            res = tr[p].val;
            p = tr[p].lc;
        }
        else
            p = tr[p].rc;
    }
    return res;
}

void printmax(int p){
    while(tr[p].rc){
        p = tr[p].rc;
    }
    printf("%d\n", tr[p].num);
    maxval = tr[p].val;
}

void printmin(int p){
    while(tr[p].lc){
        p = tr[p].lc;
    }
    printf("%d\n", tr[p].num);
    minval = tr[p].val;
}

int main(){
    int num, val;
    //freopen("input.txt", "r", stdin);
    while(scanf("%d", &n), n){
        if (n == 1){
            scanf("%d%d", &num, &val);
            Insert(rt, val, num);
        }
        else if (n == 2){
            if (rt == 0) printf("0\n");
            else{
                printmax(rt);
                Delete(rt, maxval);
            }
        }
        else if (n == 3){
            if (rt == 1) printf("0\n");
            else{
                printmin(rt);
                Delete(rt, minval);
            }
        }    
    }
    return 0;
}