题解 P1503 【鬼子进村】
Ireliaღ
2019-06-02 20:43:47
**对于非毒瘤数据，替罪羊树是所有平衡树中跑的最快的**
这道题思路就是开栈记录每次毁掉的房子，开数组记录每一个房子是否被毁，每次查询前驱和后继即可。
提供指针版替罪羊树的代码
```cpp
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
const int INF = 0x7f7f7f7f;
const int MAXN = 5e4 + 5;
const float Alpha = 0.7;
int n, m;
bool vis[MAXN];
stack<int> stk;
char op[5];
struct Node{
int val, siz, cov;
bool exist;
Node *ch[2];
Node(int val) : val(val) {
exist = true;
ch[0] = ch[1] = NULL;
siz = cov = 1;
}
};
Node *rt;
vector<Node*> vec;
stack<Node*> tsh;
Node *newNode(int val) {
if (tsh.empty()) return new Node(val);
Node *ret = tsh.top(); tsh.pop();
*ret = Node(val);
return ret;
}
void Update(Node *now) {
now->siz = now->exist + (now->ch[0] ? now->ch[0]->siz : 0) + (now->ch[1] ? now->ch[1]->siz : 0);
now->cov = 1 + (now->ch[0] ? now->ch[0]->cov : 0) + (now->ch[1] ? now->ch[1]->cov : 0);
}
bool Bad(Node *now) {
int ls = now->ch[0] ? now->ch[0]->cov : 0;
int rs = now->ch[1] ? now->ch[1]->cov : 0;
return (float)ls / now->cov > Alpha || (float)rs / now->cov > Alpha;
}
void Dfs(Node *now) {
if (!now) return;
Node *tmp = now;
Dfs(now->ch[0]);
if (now->exist) vec.push_back(now);
else tsh.push(now);
Dfs(now->ch[1]);
tmp->ch[0] = tmp->ch[1] = NULL;
}
void Rebuild(Node *&now, int l, int r) {
if (l > r) return;
int mid = l + r >> 1;
now = vec[mid];
Rebuild(now->ch[0], l, mid - 1);
Rebuild(now->ch[1], mid + 1, r);
Update(now);
}
void Insert(Node *&now, int k) {
if (!now) {
now = newNode(k);
return;
}
if (now->val == k) now->exist = true;
else if (k < now->val) Insert(now->ch[0], k);
else if (k > now->val) Insert(now->ch[1], k);
Update(now);
if (!Bad(now)) return;
vec.clear();
Dfs(now);
int len = vec.size();
Rebuild(now, 0, len - 1);
}
void Remove(Node *now, int k) {
if (!now) return;
if (now->val == k) now->exist = false;
else if (k < now->val) Remove(now->ch[0], k);
else if (k > now->val) Remove(now->ch[1], k);
Update(now);
if (!Bad(now)) return;
vec.clear();
Dfs(now);
int len = vec.size();
Rebuild(now, 0, len - 1);
}
int GetPre(Node *now, int k) {
if (!now) return -INF;
if (now->val >= k) return GetPre(now->ch[0], k);
int ret = GetPre(now->ch[1], k);
return ret == -INF ? (now->exist ? now->val : GetPre(now->ch[0], k)) : ret;
}
int GetSuc(Node *now, int k) {
if (!now) return INF;
if (now->val <= k) return GetSuc(now->ch[1], k);
int ret = GetSuc(now->ch[0], k);
return ret == INF ? (now->exist ? now->val : GetSuc(now->ch[1], k)) : ret;
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
while (m--) {
cin >> op;
if (op[0] == 'D') {
int x;
cin >> x;
Insert(rt, x);
stk.push(x);
vis[x] = true;
} else if (op[0] == 'R') {
int x = stk.top(); stk.pop();
Remove(rt, x);
vis[x] = false;
} else if (op[0] == 'Q') {
int x;
cin >> x;
if (vis[x]) {
cout << '0' << endl;
continue;
}
int l = GetPre(rt, x), r = GetSuc(rt, x);
cerr << "L:" << l << ' ' << "R:" << r << endl;
cout << (r == INF ? n + 1 : r) - (l == -INF ? 0 : l) - 1 << endl;
}
}
return 0;
}
```