Treap

为什么开个帖子因为 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，等我调下。

炸，没加 &