hdu 4217 Data Structure?/treap，hdutreap
原題鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=4217
可用線段樹寫，效率要高點。
這道題以前用c語言寫的treap水過了。。
現在接觸了c++重寫一遍。。。
不帶重復元素的插入刪除第k大帶垃圾回收，具體如下：
![]()
1 #include<cstdio>
2 #include<cstdlib>
3 #include<iostream>
4 #include<algorithm>
5 typedef long long ll;
6 const int MAX_N = 300100;
7 struct Node{
8 int v, s, fix;
9 Node *ch[2];
10 inline void
11 set(int _fix, int _v = 0, int _s = 0, Node *p = NULL){
12 fix = _fix, 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 };
19 int run(){
20 static int x = 184082857;
21 x += (x << 2) | 1;
22 return x;
23 }
24 struct Treap{
25 Node *tail, *null, *root;
26 Node stack[MAX_N];
27 int top;
28 Node *store[MAX_N];
29 void init(){
30 tail = &stack[0];
31 null = tail++;
32 null->set(0x7fffffff);
33 root = null;
34 top = 0;
35 }
36 Node *newNode(int v){
37 Node *p = null;
38 if (top) p = store[--top];
39 else p = tail++;
40 p->set(run(), v, 1, null);
41 return p;
42 }
43 void rotate(Node* &x, int d){
44 Node *k = x->ch[!d];
45 x->ch[!d] = k->ch[d];
46 k->ch[d] = x;
47 k->s = x->s;
48 x->push_up();
49 x = k;
50 }
51 void insert(Node* &x, int v){
52 if (x == null){
53 x = newNode(v);
54 return;
55 } else {
56 int d = v > x->v;
57 insert(x->ch[d], v);
58 if (x->ch[d]->fix < x->fix) rotate(x, !d);
59 x->push_up();
60 }
61 }
62 void del(Node* &x, int v){
63 if (x == null) return;
64 x->s--;
65 if (x->v == v){
66 if (x->ch[0] == null || x->ch[1] == null){
67 store[top++] = x;
68 x = x->ch[0] == null ? x->ch[1] : x->ch[0];
69 } else {
70 int d = x->ch[0]->fix < x->ch[1]->fix;
71 rotate(x, !d);
72 del(x->ch[!d], v);
73 }
74 } else {
75 del(x->ch[v>x->v], v);
76 }
77 if (x != null) x->push_up();
78 }
79 int find_kth(Node *x, int k){
80 int t = 0;
81 for (;;){
82 t = x->ch[0]->s;
83 if (k == t + 1) break;
84 else if (k < t + 1) x = x->ch[0];
85 else k -= t + 1, x = x->ch[1];
86 }
87 return x->v;
88 }
89 }treap;
90 int main(){
91 #ifdef LOCAL
92 freopen("in.txt", "r", stdin);
93 freopen("out.txt", "w+", stdout);
94 #endif
95 ll ans;
96 int t, n, m, k, tmp, c = 1;
97 scanf("%d", &t);
98 while (t--){
99 treap.init(), ans = 0;
100 scanf("%d %d", &n, &m);
101 for (int i = 1; i <= n; i++)
102 treap.insert(treap.root, i);
103 while (m--){
104 scanf("%d", &k);
105 ans += tmp = treap.find_kth(treap.root, k);
106 treap.del(treap.root, tmp);
107 }
108 printf("Case %d: %lld\n", c++, ans);
109 }
110 return 0;
111 }
View Code
