【封装】替罪羊树
NCC79601
2019-04-09 13:35:06
替罪羊树学会好久了，但是从来没有认真用$class$成功封装过。这里记录一种封装了正常$BST$操作的$class$，供以后复习使用。
实际上这是一种比较奇葩的写法，在查询前驱后继的时候比较暴力，导致常数大了一些，不过拿去跑二逼平衡树**不吸氧**也是能过的。~~暴力大法好啊~~
这里所谓的**暴力写法** 就是这个地方：
```cpp
inline int Prefix(int x, int v) {
if(!x)
return -INF;
if(v(x) < v) {
if(c(x))
return max(v(x), Prefix(r(x), v));
else
return max(Prefix(l(x), v), Prefix(r(x), v));
}
else
return Prefix(l(x), v);
}
inline int Suffix(int x, int v) {
if(!x)
return INF;
if(v(x) > v) {
if(c(x))
return min(v(x), Suffix(l(x), v));
else
return min(Suffix(r(x), v), Suffix(l(x), v));
}
else
return Suffix(r(x), v);
}
```
注意第二层$if()$的$else$，是不是非常暴力！当前节点不存在就**合并左右儿子的信息**，因为你也不知道左右儿子到底存不存在。要想完美地解决这个判断问题非常麻烦，因此我干脆就不解决了，直接拉常数解决，~~反正不太可能会TLE~~
注意使用前需要$Init()$，以为低版本C++是不支持在$private$里头初始化的。
---
完整代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const double alpha = 0.67;
const int INF = 2147483647;
class ScapeGoatTree {
#define l(x) tree[x].lson
#define r(x) tree[x].rson
#define v(x) tree[x].val
#define s(x) tree[x].size
#define c(x) tree[x].cnt
#define d(x) tree[x].del
private:
int cnt;
int cache[MAXN];
int len;
struct BST {
int lson, rson;
int val, size, cnt, del;
} tree[MAXN];
inline void update(int &x) {
s(x) = s(l(x)) + s(r(x)) + c(x);
d(x) = d(l(x)) + d(r(x)) + c(x);
return;
}
inline bool isbad(int x) {
return ((double)s(x) * alpha > d(x)) || ((double)s(x) * alpha < max(s(l(x)), s(r(x))));
}
inline void flatten(int x) {
if(!x)
return;
flatten(l(x));
if(c(x))
cache[++len] = x;
flatten(r(x));
return;
}
inline void build(int &x, int l, int r) {
if(l > r) {
x = 0;
return;
}
int mid = (l + r) >> 1;
x = cache[mid];
build(l(x), l, mid - 1);
build(r(x), mid + 1, r);
update(x);
return;
}
inline void rebuild(int &x) {
len = 0;
flatten(x);
build(x, 1, len);
return;
}
public:
inline void Init() {
cnt = len = 0;
return;
}
inline void Insert(int &x, int v) {
if(!x) {
x = ++cnt;
v(x) = v;
l(x) = r(x) = 0;
c(x) = s(x) = d(x) = 1;
return;
}
if(v == v(x)) {
c(x)++;
}
else {
if(v < v(x))
Insert(l(x), v);
else
Insert(r(x), v);
}
update(x);
if(isbad(x))
rebuild(x);
return;
}
inline void Delete(int &x, int v) {
if(!x)
return;
d(x)--;
if(v == v(x)) {
if(c(x))
c(x)--;
}
else {
if(v < v(x))
Delete(l(x), v);
else
Delete(r(x), v);
}
update(x);
if(isbad(x))
rebuild(x);
return;
}
inline int QueryKth(int x, int k) {
if(!k)
return 0;
if(d(l(x)) < k && k <= d(l(x)) + c(x))
return v(x);
else {
if(k <= d(l(x)))
return QueryKth(l(x), k);
else
return QueryKth(r(x), k - d(l(x)) - c(x));
}
}
inline int PreRank(int x, int v) {
if(!x)
return 0;
if(v == v(x))
return d(l(x));
else {
if(v < v(x))
return PreRank(l(x), v);
else
return PreRank(r(x), v) + c(x) + d(l(x));
}
}
inline int QueryRank(int x, int v) {
return PreRank(x, v) + 1;
}
inline int Prefix(int x, int v) {
if(!x)
return -INF;
if(v(x) < v) {
if(c(x)) {
if(d(r(x)))
return max(v(x), Prefix(r(x), v));
else
return v(x);
}
else {
if(d(r(x)))
return Prefix(r(x), v);
else
return Prefix(l(x), v);
}
}
else
return Prefix(l(x), v);
}
inline int Suffix(int x, int v) {
if(!x)
return INF;
if(v(x) > v) {
if(c(x)) {
if(d(l(x)))
return min(v(x), Suffix(l(x), v));
else
return v(x);
}
else {
if(d(l(x)))
return Suffix(l(x), v);
else
return Suffix(r(x), v);
}
}
else
return Suffix(r(x), v);
}
inline void Debug(int x) {
if(!x)
return;
Debug(l(x));
printf("node#%d: v=%d, l=%d, r=%d, c=%d, d=%d, s=%d\n", x, v(x), l(x), r(x), c(x), d(x), s(x));
Debug(r(x));
return;
}
};
ScapeGoatTree s;
inline int read() {
int res = 0, uz = 1;
char ch = getchar();
while(!isdigit(ch)) {
if(ch == '-')
uz = -1;
ch = getchar();
}
while(isdigit(ch)) {
res = (res << 3) + (res << 1) + (ch ^ '0');
ch = getchar();
}
return res * uz;
}
int main() {
s.Init();
int n = read();
int root = 0;
while(n--) {
int opt = read(), x = read();
switch(opt) {
case 1: {
s.Insert(root, x);
break;
}
case 2: {
s.Delete(root, x);
break;
}
case 3: {
printf("%d\n", s.QueryRank(root, x));
break;
}
case 4: {
printf("%d\n", s.QueryKth(root, x));
break;
}
case 5: {
printf("%d\n", s.Prefix(root, x));
break;
}
default: {
printf("%d\n", s.Suffix(root, x));
break;
}
}
}
return 0;
}
```