POJ

题意:有若干带有优先级P的权值K,需要维护一个数据结构回答询问,求最高或最低优先级的权值并删除。

裸平衡树。但我只会treap……
这里的删除因为最多只有一个孩子所以不必另写一个函数,只是删除需要的处理有点多,在这里卡了一上午。

指针版

#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}

struct Node
{
    Node *ch[2];
    int r;
    int p, k;
    Node(int p = -1, int k = -1, int d = -1) : p(p), k(k), r(d){ch[0] = ch[1] = NULL;}
    int cmp(int x){return x == p ? -1 : ((x < p) ? 0 : 1);}
} *root;

void rotate(Node* &o, int d)
{
    Node *k = o -> ch[d ^ 1];
    o -> ch[d ^ 1] = k -> ch[d];
    k -> ch[d] = o;
    o = k;
}

void insert(Node* &o, int k, int p)
{
    if(!o){o = new Node(p, k, rand());}
    else
    {
        int d = o -> cmp(p);
        insert(o -> ch[d], k, p);
        if((o -> ch[d] -> r)  >  (o -> r))
            rotate(o, d ^ 1);
    }
}

void remove(Node* &o, int x)
{
    int d = o -> cmp(x);
    if(d == -1)
    {
        if(!o -> ch[0])
            o = o -> ch[1];
        else if(!o -> ch[1])
            o = o -> ch[0];
        else
        {
            int d2 = ((o -> ch[0] -> r) > (o -> ch[1] -> r) ? 1 : 0);
            rotate(o, d2);
            remove(o -> ch[d2], x);
        }
    }
    else
        remove(o -> ch[d], x);
}

int find(Node* o, int d)
{
    while(o && o -> ch[d ^ 1])
        o = o -> ch[d ^ 1];
    if(!o)
        return 0;
    int ret = o -> k;
    remove(root, o -> p);
    return ret;
}

int main()
{
    srand(233);
    int code;
    root = NULL;
    while(read(code), code != 0)
    {
        if(code == 1)
        {
            int k, p;
            read(k, p);
            insert(root, k, p);
        }
        else
            printf("%d\n", find(root, code - 2));
    }
    return 0;
}

数组版

#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}

const int maxn = 1e6 + 10;

struct node
{
    int p, k, r;
    int ch[2];
    node(int a = 0, int b = 0, int c = -1) : k(a), p(b), r(c){ch[0] = ch[1] = 0;}
} T[maxn];
int cnt = 1, root = 0;

inline bool cmp(int o, int x){return T[o].p == x ? -1 : ((T[o].p > x) ? 0 : 1);}

void rotate(int &o, int d)
{
    int p = T[o].ch[d ^ 1];    
    T[o].ch[d ^ 1] = T[p].ch[d];
    T[p].ch[d] = o;    
    o = p;
}

void insert(int &o, int v, int w)
{
    if(o == 0)
        T[o = cnt++] = node(v, w, rand());
    else
    {
        int d = cmp(o, w);
        insert(T[o].ch[d], v, w);
        if(T[T[o].ch[d]].r > T[o].r)
            rotate(o, d ^ 1);
    }
}

int find(int o, int d)
{
    int x = o;
    while(o && T[o].ch[d ^ 1])
        x = o, o = T[o].ch[d ^ 1];
    if(o == 0)
        return 0;
    if(o != root)
        T[x].ch[d ^ 1] = T[o].ch[d];
    else
        root = T[o].ch[d];
    int ret = T[o].k;
    if(o == root && !T[o].ch[d])
        T[o] = node(), root = 0;
    return ret;
}

int main()
{
    srand(233);
    int code;
    while(read(code), code != 0)
    {
        if(code == 1)
        {
            int v, w;
            read(v, w);
            insert(root, v, w);
        }
        else
            printf("%d\n", find(root, code - 2));
    }
    return 0;
}

标签: none

添加新评论