Various Blog

ScrapeGoatTree 模板

2018-11-25 09:21:23


//P3369
#include <bits/stdc++.h>

namespace SGT{
    const double alpha = 0.7;
    inline int max(int a,int b){
        return (a>b?a:b);
    }

    struct node{
        node *lc,*rc;
        int v,sz,valid;
        bool del;

        inline bool bad(){
            return (double)max((lc != NULL?lc->sz:0),(rc != NULL?rc->sz:0)) \
            > (double)sz * alpha;
        }

        inline void update(){
            sz = !del + (lc != NULL?lc->sz:0) + (rc != NULL?rc->sz:0);
            valid = !del + (lc != NULL?lc->valid:0) + (rc != NULL?rc->valid:0);
        }
    }*Root;

    void Dfs(node* &o,std::vector<node*> &vc){
        if (o == NULL) return;
        if (o->lc != NULL) Dfs(o->lc,vc);
        if (!o->del) vc.push_back(o);
        if (o->rc != NULL) Dfs(o->rc,vc);
        if (o->del) delete o;
    }

    node *Build(std::vector<node*> &vc,int l,int r){
        if (l >= r) return NULL;

        int mid = (l+r)>>1;
        node *o = vc[mid];
        o->lc = Build(vc,l,mid);
        o->rc = Build(vc,mid+1,r);
        o->update();

        return o;
    }

    void Rebuild(node* &o){
        std::vector<node*> vc;
        Dfs(o,vc);
        o = Build(vc,0,vc.size());
    }

    void Insert(node* &o,int x){
        if (o == NULL){
            o = new node;
            o->lc = o->rc = NULL;
            o->sz = o->valid = 1;
            o->v = x;
            o->del = false;
            return;
        }

        o->sz++;o->valid++;
        if (x < o->v)
            Insert(o->lc,x);
        else
            Insert(o->rc,x);

        o->update();
        if (o->bad()) Rebuild(o);
    }

    void Delete(node* &o,int rnk){
        if (o == NULL) return;
        if (!o->del && (o->lc != NULL?o->lc->valid:0) + 1 == rnk){
            o->del = true;
            o->valid --;
            return;
        }

        o->valid --;
        if (rnk <= (o->lc != NULL?o->lc->valid:0) + !o->del)
            Delete(o->lc,rnk);
        else
            Delete(o->rc,rnk - (o->lc != NULL?o->lc->valid:0) - !o->del);
    }

    int GetRank(node* o,int x){
        int ans = 1;
        while (o != NULL){
            if (o->v>=x)
                o = o->lc;
            else{
                ans += (o->lc != NULL?o->lc->valid:0) + !o->del;
                o = o->rc;
            }
        }

        return ans;
    }

    int FindKth(node* o,int rnk){
        while (o != NULL){
            if (!o->del && (o->lc != NULL?o->lc->valid:0) + 1 == rnk)
                return o->v;

            if ((o->lc != NULL?o->lc->valid:0) >= rnk)
                o = o->lc;
            else{
                rnk -= (o->lc != NULL?o->lc->valid:0) + !o->del;
                o = o->rc;
            }
        }

        return -1;
    }

    int Frontier(node* o,int x){
        return FindKth(o,GetRank(o,x)-1);
    }

    int Latier(node* o,int x){
        return FindKth(o,GetRank(o,x+1));
    }
} 

int n,opt,x;

int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin>>n;

    while (n--){
        std::cin>>opt>>x;
        if (opt == 1) SGT::Insert(SGT::Root,x);
        if (opt == 2) SGT::Delete(SGT::Root,GetRank(SGT::Root,x));
        if (opt == 3) std::cout<<SGT::GetRank(SGT::Root,x)<<std::endl; 
        if (opt == 4) std::cout<<SGT::FindKth(SGT::Root,x)<<std::endl;
        if (opt == 5) std::cout<<SGT::Frontier(SGT::Root,x)<<std::endl;
        if (opt == 6) std::cout<<SGT::Latier(SGT::Root,x)<<std::endl ;
    }

    return 0;
}