鬼子进村题解
2026-04-06 19:59:56
发布于：浙江
30阅读
0回复
0点赞
鬼子进村了，在 P1503。
这里开三个数据结构用来维护：
- 栈：由操作一、二可得，我们需要用一个栈来维护被炸毁的房子，因为操作二中要取上一个被炸毁的房子。
- 布尔数组：或许称不上数据结构。这里用来储存房子是否被炸毁。
- 平衡树（Treap）：也是维护房子是否被炸毁，不过这里主要用于任务三。我们可以发现当前房子所能到达的房子数量就是当前房子的后缀减去前缀减去 。
那么代码可得。注意哨兵需要改成 和 ，不然你就会像我一样获得十分的高分 QAQ；还要注意如果当前房子已经被炸毁了直接输出 。
#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;
}
有帮助，赞一个