萌新第二次求助

回复帖子

@AquaRio  2019-10-09 23:33 回复

4-10 RE

12 WA

窝写的是指针替罪羊树...

#include<bits/stdc++.h>
using namespace std;

const double alpha=0.7;

struct node{
    node *l,*r;
    int val,size,cnt;
    bool deleted;
    bool isbad(){return l->cnt>alpha*cnt+5||r->cnt>alpha*cnt+5;}
    void maintain(){size=!deleted+l->size+r->size;cnt=1+l->cnt+r->cnt;}
}; 

node *null;

void dfs(node *o,vector<node*> &v){
    if(o==null) return;
    dfs(o->l,v);
    if(!o->deleted) v.push_back(o);
    dfs(o->r,v);
    if(o->deleted) delete o;
}

node *build(vector<node*> &v,int l,int r){
    if(l>=r) return null;
    int mid=(l+r)>>1;
    node *o=v[mid];
    o->l=build(v,l,mid);
    o->r=build(v,mid+1,r);
    o->maintain();
    return o;
}

void rebuild(node* o){
    vector<node*> v;
    dfs(o,v);
    o=build(v,0,v.size());
}

void insert(int x,node* &o){
    if(o==null){
        o=new node;
        o->l=o->r=null;
        o->deleted=false;
        o->size=o->cnt=1;
        o->val=x;
        return; 
    }
    else{
        ++o->size;
        ++o->cnt;
        if(x>=o->val)
            insert(x,o->r);
        else
            insert(x,o->l);
        if(o->isbad()) rebuild(o);
    }
}

int rank(node *now,int x){
    int ans=1;
    while(now!=null){
        if(now->val>=x) now=now->l;
        else{
            ans+=now->l->size+!now->deleted;
            now=now->r;
        }
    }
    return ans;
}

int kth(node *now,int x){
    while(now!=null){
        if(!now->deleted and now->l->size+1==x)
            return now->val;
        if(now->l->size>=x) now=now->l;
        else{
            x-=now->l->size+!now->deleted;
            now=now->r; 
        }
    }
}

void erase(node *o,int rk){
    if(!o->deleted and rk==o->l->size+1){
        o->deleted=1;
        --o->size;
        return;
    }
    --o->size;
    if(rk<=o->l->size+!o->deleted)
        erase(o->l,rk);
    else erase(o->r,rk-o->l->size-!o->deleted);
}

node *root;

int main(){
    null=new node;
    root=null;
    int n;
    scanf("%d",&n);
    while(n--){
        int opt,x;
        scanf("%d%d",&opt,&x);
        if(opt==1) insert(x,root);
        if(opt==2) erase(root,rank(root,x));
        if(opt==3) cout<<rank(root,x)<<endl;
        if(opt==4) cout<<kth(root,x)<<endl;
        if(opt==5) cout<<kth(root,rank(root,x)-1)<<endl;
        if(opt==6) cout<<kth(root,rank(root,x+1))<<endl;
    } 
    return 0;
}
@AquaRio  2019-10-09 23:45 回复 举报

话说窝AC的32分的点都不用rebuild

数据还是有点毒瘤的

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。