sinEagle

bottlecode

0%

POJ3481 Double Queue （平衡树）

发表于
本文字数： 2.9k 阅读时长 ≈ 3 分钟

题目链接

直接用Treap写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;

const int N = 1e6 + 10;
int n, k, p;
struct node {
    int id;
    int val;
};
int cnt = 0;
struct Treap {
    Treap *L, *R;
    int fix, size;
    node val;
    void Init() { L = R = NULL; };
    inline int lsize() { return L ? L->size : 0;  };
    inline int rsize() { return R ? R->size : 0;  };
} Node[N], *root;

Treap* NewNode () {
    Node[cnt].Init();
    return Node + cnt++;
}

void Recount(Treap *&p) {
    p->size = p->lsize() + p->rsize() + 1;
}

void Treap_R_Rot(Treap *&a) {
    Treap *b = a->L;
    a->L = b->R;
    b->R = a;
    a = b;
    Recount(a->R);
    Recount(a);
}

void Treap_L_Rot(Treap *&a) {
    Treap *b = a->R;
    a->R = b->L;
    b->L = a;
    a = b;
    Recount(a->L);
    Recount(a);
}

void Treap_insert(Treap *&p, node val) {
    if(!p) {
        p = NewNode();
        p->val = val;
        p->size = 1;
        p->fix = rand();
        //printf("success insert!\n");
    } else if(val.val <= p->val.val) {
        p->size++;
        Treap_insert(p->L, val);
        if(p->L->fix < p->fix)
            Treap_R_Rot(p);
    } else {
        p->size++;
        Treap_insert(p->R, val);
        if(p->R->fix < p->fix)
            Treap_L_Rot(p);
    }
}

void Find_Max(Treap *& p) {
    if(p->R == NULL) {
        printf("%d\n", p->val.id);
        //printf("success del!\n");
        if(p->L != NULL)
            p = p->L;
        else p = p->R;
        return;
    }
    p->size--;
    return Find_Max(p->R);
}

void Find_Min(Treap *& p) {
    if(p->L == NULL) {
        printf("%d\n", p->val.id);
        //printf("success del!\n");
        if(p->R != NULL)
            p = p->R;
        else p = p->L;
        return;
    }
    p->size--;
    return Find_Min(p->L);
}


int main() {
    while(scanf("%d", &n) != EOF) {
        if(n == 0) break;
        if(n == 1) {
            scanf("%d%d", &k, &p);
            Treap_insert(root, node{k, p});
           
        } else {
            if(root == NULL) {
                printf("0\n");
                continue;
            }
            if(n == 2) {
                Find_Max(root); 
            }else if(n == 3) {
                Find_Min(root);
            }
        }
    }

    return 0;
}

STL里的 map 内部用红黑树实现，可直接用map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;

map<int, int> a;
int n, k, p;

int main() {
    map<int, int>::iterator it;
    while(scanf("%d", &n), n) {
        if(n == 1) {
            scanf("%d%d", &k, &p);
            a[p] = k;
        } else {
            if(a.empty())
                printf("0\n");
            else {
                if(n == 2) {
                    it = a.end();
                    it--;
                } else if(n == 3)
                    it = a.begin();
                printf("%d\n", it->second);
                a.erase(it->first);
            }
        }
    }

    return 0;
}
求大佬赏个饭