Treap
2026-04-06 19:41:47
发布于：浙江
45阅读
0回复
0点赞
为什么开个帖子因为 ACGO 的编译器老被炸，之前我写 ABC 的时候 D 的代码就没了。
ACGO 的老年编译器缩进怎么没了
吃个饭
#include <bits/stdc++.h>
const int INF=1e9;
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(-INF),*mx=newnode(INF);//哨兵节点
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));
}void slove(){
int op,x;
std::cin >> op >> x;
switch(op){
case 1:push(root,x);break;
case 2:del(root,x);break;
case 3:std::cout << krank(root,x) << std::endl;break;
case 4:std::cout << kth(root,x+1) << std::endl;break;
case 5:std::cout << pre(root,x) << std::endl;break;
case 6:std::cout << nxt(root,x) << std::endl;break;
}
}
int main(){
std::ios::sync_with_stdio(false); // 修复5
std::cin.tie(0);
srand(time(0));
build();
int t;
std::cin >> t;
while(t--){
slove();
}
return 0;
}
但是 RE，等我调下。
炸，没加 &
有帮助，赞一个