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
| template<class T, size_t size>
struct MemoryPool {
T buf[size], *st[size], *tail, *end;
int top;
MemoryPool() : top(0), tail(buf), end(buf + size) {}
inline T *alloc() {
if (top) return st[--top];
if (tail != end) return tail++;
return new T;
}
inline void recycle(T *x) {
if (top > size) delete x;
else st[top++] = x;
}
};
#ifndef ARNE_ANDERSSON_TREE
#define ARNE_ANDERSSON_TREE
template<class T, size_t MAXN>
struct AATree {
struct Node {
Node *ch[2];
int size, level;
T data;
inline Node *init(const T &data) { return size = level = 1, this->data = data, this; }
Node(): size(0), level(0) { ch[0] = ch[1] = this; }
} *null, *root;
MemoryPool<Node, MAXN> pool;
inline void rotate(Node *&p, bool x) {
if (p->level == p->ch[x]->ch[x]->level) {
Node *o = p;
p = p->ch[x], o->ch[x] = p->ch[!x], p->ch[!x] = o;
if (x)p->level++;
p->size = o->size, o->size = o->ch[0]->size + o->ch[1]->size + 1;
}
}
inline void eraseFix(Node *&o) {
if (o ->ch[0]->level < o->level - 1 || o->ch[1]->level < o->level - 1) {
if (o->ch[1]->level > --o->level)o->ch[1]->level = o->level;
rotate(o, 0);
if (o->ch[1]->size) rotate(o->ch[1], 0);
if (o->ch[1]->ch[1]->size) rotate(o->ch[1]->ch[1], 0);
rotate(o, 1);
if (o->ch[1]->size) rotate(o->ch[1], 1);
}
}
inline void insert(Node *&o, const T&data) {
if (!o->size) o = pool.alloc()->init(data), o->ch[0] = o->ch[1] = null;
else o->size++, insert(o->ch[o->data < data], data), rotate(o, 0), rotate(o, 1);
}
inline bool erase(Node *&o, const T &data) {
if (!o->size)return 0;
if (o->data == data) {
if (!o->ch[0]->size || !o->ch[1]->size) {
Node *t = o;
o = o->ch[0]->size ? o->ch[0] : o->ch[1], pool.recycle(t);
} else {
o->size--;
Node *t = o->ch[1];
while (t->ch[0]->size) t = t->ch[0];
o->data = t->data, erase(o->ch[1], t->data), eraseFix(o);
}
return 1;
} else if (erase(o->ch[o->data < data], data)) {
return o->size--, eraseFix(o), 1;
} else return 0;
}
inline void clear(Node *&o) { if (o->size) clear(o->ch[0]), clear(o->ch[1]), pool.recycle(o); }
AATree(): null(pool.alloc()) { root = null->ch[0] = null->ch[1] = null; }
inline void clear() {clear(root), root = null;}
inline void insert(const T&data) { insert(root, data); }
inline bool erase(const T&data) { return erase(root, data); }
inline bool find(const T &data) {
Node *o = root;
while (o->size && o->data != data)o = o->ch[o->data < data];
return o->size ? 1 : 0;
}
inline int rank(const T &data) {
register int cnt = 0;
for (Node *o = root; o->size;) {
if (o->data < data) cnt += o->ch[0]->size + 1, o = o->ch[1];
else o = o->ch[0];
}
return cnt;
}
inline const T &select(int k) {
for (Node *o = root;;) {
if (k <= o->ch[0]->size)o = o->ch[0];
else if (k == o->ch[0]->size + 1) return o->data;
else k -= o->ch[0]->size + 1, o = o->ch[1];
}
}
inline const T &operator [] (int k) { return select(k); }
inline const T &precursor(const T &data) {
Node *x = root, *y = 0;
while (x->size) {
if (x->data < data) y = x, x = x->ch[1];
else x = x->ch[0];
}
if (y) return y->data;
return data;
}
inline const T &successor(const T &data) {
Node *x = root, *y = 0;
while (x->size) {
if (data < x->data) y = x, x = x->ch[0];
else x = x->ch[1];
}
if (y) return y->data;
return data;
}
inline int size() { return root->size; }
};
#endif
|
