hdu 5249 KPI，hdu5249kpi
題目連接
http://acm.hdu.edu.cn/showproblem.php?pid=5249
KPI
Description
你工作以後, KPI 就是你的全部了. 我開發了一個服務，取得了很大的知名度。數十億的請求被推到一個大管道後同時服務從管頭拉取請求。讓我們來定義每個請求都有一個重要值。我的KPI是由當前管道內請求的重要值的中間值來計算。現在給你服務記錄，有時我想知道當前管道內請求的重要值得中間值。
Input
有大約100組數據。
每組數據第一行有一個n(1≤n≤10000)，代表服務記錄數。
接下來有n行，每一行有3種形式
"in x": 代表重要值為x(0≤x≤109)的請求被推進管道。
"out": 代表服務拉取了管道頭部的請求。
"query: 代表我想知道當前管道內請求重要值的中間值. 那就是說，如果當前管道內有m條請求, 我想知道，升序排序後第$floor(m/2)+1_{th}$ 條請求的重要值.
為了讓題目簡單，所有的x都不同，並且如果管道內沒有值，就不會有"out"和"query"操作。
Output
對於每組數據，先輸出一行
Case #i:
然後每一次"query"，輸出當前管道內重要值的中間值。
Sample Input
6
in 874
query
out
in 24622
in 12194
query
Sample Output
Case #1:
874
24622
紅黑樹：
![]()
1 #include<algorithm>
2 #include<iostream>
3 #include<cstdlib>
4 #include<cstring>
5 #include<cstdio>
6 #include<queue>
7 using std::queue;
8 const int Max_N = 10010;
9 struct Node {
10 int data, s;
11 bool color;
12 Node *fa, *ch[2];
13 inline void set(int _v, int i, bool _color, Node *p) {
14 data = _v, color = _color, s = i;
15 fa = ch[0] = ch[1] = p;
16 }
17 inline void push_up() {
18 s = ch[0]->s + ch[1]->s + 1;
19 }
20 inline void push_down() {
21 for (Node *x = this; x->s; x = x->fa) x->s--;
22 }
23 };
24 struct RedBlackTree {
25 int top;
26 Node *root, *null;
27 Node stack[Max_N], *tail, *store[Max_N];
28 void init() {
29 tail = &stack[0];
30 null = tail++;
31 null->set(0, 0, 0, NULL);
32 root = null;
33 top = 0;
34 }
35 inline Node *newNode(int v) {
36 Node *p = null;
37 if (!top) p = tail++;
38 else p = store[--top];
39 p->set(v, 1, 1, null);
40 return p;
41 }
42 inline void rotate(Node* &x, bool d) {
43 Node *y = x->ch[!d];
44 x->ch[!d] = y->ch[d];
45 if (y->ch[d] != null) y->ch[d]->fa = x;
46 y->fa = x->fa;
47 if (x->fa == null) root = y;
48 else x->fa->ch[x->fa->ch[0] != x] = y;
49 y->ch[d] = x;
50 x->fa = y;
51 y->s = x->s;
52 x->push_up();
53 }
54 inline void insert(int v) {
55 Node *x = root, *y = null;
56 while (x->s){
57 x->s++;
58 y = x, x = x->ch[v > x->data];
59 }
60 x = newNode(v);
61 if (y != null) y->ch[v > y->data] = x;
62 else root = x;
63 x->fa = y;
64 insert_fix(x);
65 }
66 inline void insert_fix(Node* &x) {
67 while (x->fa->color){
68 Node *par = x->fa, *Gp = par->fa;
69 bool d = par == Gp->ch[0];
70 Node *uncle = Gp->ch[d];
71 if (uncle->color) {
72 par->color = uncle->color = 0;
73 Gp->color = 1;
74 x = Gp;
75 } else if (x == par->ch[d]) {
76 rotate(x = par, !d);
77 } else {
78 Gp->color = 1;
79 par->color = 0;
80 rotate(Gp, d);
81 }
82 }
83 root->color = 0;
84 }
85 inline Node *find(Node *x, int data) {
86 while (x->s && x->data != data) x = x->ch[x->data < data];
87 return x;
88 }
89 inline void del_fix(Node* &x) {
90 while (x != root && !x->color) {
91 bool d = x == x->fa->ch[0];
92 Node *par = x->fa, *sibling = par->ch[d];
93 if (sibling->color) {
94 sibling->color = 0;
95 par->color = 1;
96 rotate(x->fa, !d);
97 sibling = par->ch[d];
98 } else if (!sibling->ch[0]->color && !sibling->ch[1]->color) {
99 sibling->color = 1, x = par;
100 } else {
101 if (!sibling->ch[d]->color) {
102 sibling->ch[!d]->color = 0;
103 sibling->color = 1;
104 rotate(sibling, d);
105 sibling = par->ch[d];
106 }
107 sibling->color = par->color;
108 sibling->ch[d]->color = par->color = 0;
109 rotate(par, !d);
110 break;
111 }
112 }
113 x->color = 0;
114 }
115 inline void del(int data) {
116 Node *z = find(root, data);
117 if (!z->s) return;
118 Node *y = z, *x = null;
119 if (z->ch[0]->s && z->ch[1]->s) {
120 y = z->ch[1];
121 while (y->ch[0]->s) y = y->ch[0];
122 }
123 x = y->ch[!y->ch[0]->s];
124 x->fa = y->fa;
125 if (!y->fa->s) root = x;
126 else y->fa->ch[y->fa->ch[1] == y] = x;
127 if (z != y) z->data = y->data;
128 y->fa->push_down();
129 if (!y->color) del_fix(x);
130 store[top++] = y;
131 }
132 inline int kth(int k) {
133 int t = 0;
134 Node *x = root;
135 for (; x->s;){
136 t = x->ch[0]->s;
137 if (k == t + 1) break;
138 else if (k <= t) x = x->ch[0];
139 else k -= t + 1, x = x->ch[1];
140 }
141 return x->data;
142 }
143 int operator[] (int k) {
144 return kth(k);
145 }
146 }rbt;
147 int main(){
148 #ifdef LOCAL
149 freopen("in.txt", "r", stdin);
150 freopen("out.txt", "w+", stdout);
151 #endif
152 int n, v, c = 1;
153 char buf[100];
154 while (~scanf("%d", &n)) {
155 rbt.init(); queue<int> q;
156 printf("Case #%d:\n", c++);
157 while (n--) {
158 scanf("%s", buf);
159 if ('i' == buf[0]) {
160 scanf("%d", &v);
161 rbt.insert(v), q.push(v);
162 } else if ('o' == buf[0]) {
163 v = q.front(); q.pop();
164 rbt.del(v);
165 } else {
166 printf("%d\n", rbt[((int)q.size() >> 1) + 1]);
167 }
168 }
169 }
170 return 0;
171 }
View Code
sb樹：
![]()
1 #include<iostream>
2 #include<cstdlib>
3 #include<cstring>
4 #include<cstdio>
5 #include<queue>
6 using std::queue;
7 const int Max_N = 10010;
8 struct Node {
9 int v, s;
10 Node *ch[2];
11 inline void set(int _v, int _s, Node *p) {
12 v = _v, s = _s;
13 ch[0] = ch[1] = p;
14 }
15 inline void push_up() {
16 s = ch[0]->s + ch[1]->s + 1;
17 }
18 inline int cmp(int x) const {
19 return x == v ? -1 : x > v;
20 }
21 };
22 struct SizeBalanceTree {
23 Node stack[Max_N];
24 Node *root, *null, *tail;
25 Node *store[Max_N];
26 int top;
27 void init() {
28 tail = &stack[0];
29 null = tail++;
30 null->set(0, 0, NULL);
31 root = null;
32 top = 0;
33 }
34 inline Node *newNode(int v) {
35 Node *p = null;
36 if (top) p = store[--top];
37 else p = tail++;
38 p->set(v, 1, null);
39 return p;
40 }
41 inline void rotate(Node* &x, int d) {
42 Node *k = x->ch[!d];
43 x->ch[!d] = k->ch[d];
44 k->ch[d] = x;
45 k->s = x->s;
46 x->push_up();
47 x = k;
48 }
49 inline void Maintain(Node* &x, int d) {
50 if (x->ch[d] == null) return;
51 if (x->ch[d]->ch[d]->s > x->ch[!d]->s) {
52 rotate(x, !d);
53 } else if (x->ch[d]->ch[!d]->s > x->ch[!d]->s) {
54 rotate(x->ch[d], d), rotate(x, !d);
55 } else {
56 return;
57 }
58 Maintain(x, 0), Maintain(x, 1);
59 }
60 inline void insert(Node* &x, int v) {
61 if (x == null) {
62 x = newNode(v);
63 return;
64 } else {
65 x->s++;
66 int d = x->cmp(v);
67 insert(x->ch[d], v);
68 x->push_up();
69 Maintain(x, d);
70 }
71 }
72 inline void del(Node* &x, int v) {
73 if (!x->s) return;
74 x->s--;
75 int d = x->cmp(v);
76 if (-1 == d) {
77 if (!x->ch[0]->s || !x->ch[1]->s) {
78 store[top++] = x;
79 x = x->ch[0]->s ? x->ch[0] : x->ch[1];
80 } else {
81 Node *ret = x->ch[1];
82 for (; ret->ch[0] != null; ret = ret->ch[0]);
83 del(x->ch[1], x->v = ret->v);
84 }
85 } else {
86 del(x->ch[d], v);
87 }
88 if (x->s) x->push_up();
89 }
90 inline void insert(int v) {
91 insert(root, v);
92 }
93 inline void del(int v) {
94 del(root, v);
95 }
96 inline int kth(int k) {
97 int t;
98 Node *x = root;
99 for (; x->s;) {
100 t = x->ch[0]->s;
101 if (k <= t) x = x->ch[0];
102 else if (t + 1 == k) break;
103 else k -= t + 1, x = x->ch[1];
104 }
105 return x->v;
106 }
107 int operator[] (int k) {
108 return kth(k);
109 }
110 }sbt;
111 int main(){
112 #ifdef LOCAL
113 freopen("in.txt", "r", stdin);
114 freopen("out.txt", "w+", stdout);
115 #endif
116 int n, v, c = 1;
117 char buf[100];
118 while (~scanf("%d", &n)) {
119 sbt.init(); queue<int> q;
120 printf("Case #%d:\n", c++);
121 while (n--) {
122 scanf("%s", buf);
123 if ('i' == buf[0]) {
124 scanf("%d", &v);
125 sbt.insert(v), q.push(v);
126 } else if ('o' == buf[0]) {
127 v = q.front(); q.pop();
128 sbt.del(v);
129 } else {
130 printf("%d\n", sbt[((int)q.size() >> 1) + 1]);
131 }
132 }
133 }
134 return 0;
135 }
View Code
簡單題沒啥說的，比較了一下還是紅黑樹快一些。。
