#创作计划#浅谈 AVL 树和红黑树-4
2026-08-10 21:08:44
发布于：浙江
44阅读
0回复
0点赞
还有第四关。这里主要讲一些关于平衡树的例题，不局限于红黑树 AVL 树。然后 AVL 树已经死了（
P1503
依旧冷饭重炒，以前是写过的（复制粘贴水一下喽 QAQ）。
这里开三个数据结构用来维护：
- 栈：由操作一、二可得，我们需要用一个栈来维护被炸毁的房子，因为操作二中要取上一个被炸毁的房子。
- 布尔数组：或许称不上数据结构。这里用来储存房子是否被炸毁。
- 平衡树（Treap）：也是维护房子是否被炸毁，不过这里主要用于任务三。我们可以发现当前房子所能到达的房子数量就是当前房子的后缀减去前缀减去 。
那么代码可得。注意哨兵需要改成 和 ，不然你就会像我一样获得十分的高分 QAQ；还要注意如果当前房子已经被炸毁了直接输出 。Treap 在本题中和红黑树作用相同。
#include <bits/stdc++.h>
const int INF=1e9;
bool vis[100004];
int n;
std::stack<int> st;
struct Treap{
int key,val,cnt,siz;//BST权值，heap权值，该数个数，子数大小
Treap* l;
Treap* r;
};
Treap* root;
Treap* newnode(int key){
Treap* node=new Treap();
node->key=key,node->val=std::rand(),node->cnt=1,node->siz=1,node->l=node->r=nullptr;
return node;
}void pushup(Treap* u){
int left_child=u->l?u->l->siz:0,right_child=u->r?u->r->siz:0;
u->siz=left_child+right_child+u->cnt;
}void build(){
Treap* mn=newnode(0),*mx=newnode(n+1);//哨兵节点
root=mn;
root->r=mx;
pushup(root);
}void zig(Treap*&u){//右旋
Treap* left_child=u->l;
u->l=left_child->r,left_child->r=u,u=left_child;
pushup(u->r),pushup(u);
}void zag(Treap*&u){//左旋
Treap* right_child=u->r;
u->r=right_child->l,right_child->l=u,u=right_child;
pushup(u->l),pushup(u);
}void push(Treap*&u,int key){
if(!u)u=newnode(key);
else{
if(u->key==key){u->cnt++;}
else if(u->key>key){
push(u->l,key);
if(u->l->val>u->val)zig(u);
}else{
push(u->r,key);
if(u->r->val>u->val)zag(u);
}
}pushup(u);
}void del(Treap*&u,int key){//删除
if(!u)return ;
else{
if(u->key==key){
if(u->cnt>1){u->cnt--;}
else{
if(u->l or u->r){
if(!u->r or (u->l and u->l->val>u->r->val))zig(u),del(u->r,key);
else zag(u),del(u->l,key);
}else{delete u,u=nullptr;return;}
}
}else{
if(u->key>key)del(u->l,key);
else del(u->r,key);
}
}if(u)pushup(u);
}int kth(Treap* u,int k){//第 k 小
int left_child=u->l?u->l->siz:0;
if(left_child>=k)return kth(u->l,k);
else if(left_child+u->cnt>=k)return u->key;
else return kth(u->r,k-left_child-u->cnt);
}int krank(Treap* u,int k){//k 的排名
if(!u)return 0;
int left_child=u->l?u->l->siz:0;
if(u->key==k)return left_child;
if(u->key>k)return krank(u->l,k);
else return left_child+u->cnt+krank(u->r,k);
}int pre(Treap* u,int key){//前驱
if(!u)return INT_MIN;
if(u->key>=key)return pre(u->l,key);
else return std::max(u->key,pre(u->r,key));
}int nxt(Treap* u,int key){//前驱
if(!u)return INT_MAX;
if(u->key<=key)return nxt(u->r,key);
else return std::min(u->key,nxt(u->l,key));
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
srand(time(0));
std::cin >> n;
int t;
std::cin >> t;
build();
while(t--){
char op;
int x;
std::cin >> op;
if(op=='D'){
std::cin >> x;
st.push(x);
vis[x]=true;
push(root,x);
}else if(op=='R'){
del(root,st.top());
vis[st.top()]=false;
st.pop();
}else{
std::cin >> x;
std::cout << (!vis[x]?nxt(root,x)-pre(root,x)-1:0) << std::endl;
}
}
return 0;
}
P17233
诶这不是黄吗为什么平衡树。
知道你很急那你就急吧，平衡树能做。讲一下核弹打蚊子咋写 QAQ
我们不关心 数组的值，只对下标进行维护。
先打表完全平方数。对于每一轮删除，我们利用平衡树求第 小的函数获取要删除数对应的下标。然后直接利用删除函数即可。这里需要用到的函数为：插入，删除，第 小，判空。
如果你是平衡树那么你需要大肆卡常，这边为了卡常代码已经成一坨了，就不放了。值得注意的是平衡树存的是原始元素下标，别输了个下标出去 QAQ。
（不是正解请勿尝试）
有帮助，赞一个