2018-team4-modules-替罪羊树

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
const double alpha = 0.75; //重建条件
struct Node{
    Node *ch[2];
    int key,siz,cnt;
    bool exist;
    void update(){
        siz = ch[0]->siz + ch[1]->siz + exist;
        cnt = ch[0]->cnt + ch[1]->cnt + 1;
    }
    bool pa(){
        return (ch[0]->cnt > cnt*alpha + 5) || (ch[1]->cnt > cnt*alpha + 5);
    }
};
struct STree{
    Node mem_poor[maxn];
    Node *tail,*root,*null;
    Node *bc[maxn];
    int bc_top;
    Node* NewNode(int key){
        Node *p = bc_top ? bc[--bc_top] : tail++;
        p->ch[0] = p->ch[1] = null;p->key = key;
        p->siz = p->cnt = 1;p->exist = true;
        return p;
    }
    void Travel(Node *p,vector<Node*>&v){ //重建
        if(p == null) return;
        Travel(p->ch[0],v);
        if(p->exist) v.push_back(p);
        else bc[bc_top++] = p;
        Travel(p->ch[1],v);
    }
    Node* Divide(vector<Node*>&v,int l,int r){ //重建
        if(l >= r) return null;
        int mid = l+r >> 1;
        Node *p = v[mid];
        p->ch[0] = Divide(v,l,mid);
        p->ch[1] = Divide(v,mid+1,r);
        p->update();return p;
    }
    void Rebuild(Node* &p){ //重建函数
        static vector<Node*>v;v.clear();
        Travel(p,v);p = Divide(v,0,v.size());
    }
    Node** Insert(Node* &p,int val){ //在p的子树中插入元素val
        if(p == null){
            p = NewNode(val);
            return &null;
        }else{
            ++(p->siz);++(p->cnt);
            Node **res = Insert(p->ch[val >= p->key],val);
            if(p->pa()) res = &p;
            return res;
        }
    }
    void Erase(Node *p,int id){ //在p的子树中删除元素id
        --(p->siz);
        int x = p->ch[0]->siz + p->exist;
        if(p->exist && id == x){
            p->exist = false;
            return;
        }else{
            if(id <= x) Erase(p->ch[0],id);
            else Erase(p->ch[1],id - x);
        }return;
    }
    void init(){
        tail = mem_poor;
        null = tail++;
        null->ch[0] = null->ch[1] = null;
        null->cnt = null->siz = null->key = 0;
        root = null;bc_top = 0;
    }
    STree(){init();}
    void Insert(int val){ //插入元素val
        Node** p = Insert(root,val);
        if(*p != null) Rebuild(*p);
    }
    int Rank(int val){ // 求出数val在元素中的排名
        Node *nw = root;
        int ret = 1;
        while(nw != null){
            if(nw->key >= val) nw = nw->ch[0];
            else{
                ret += nw->ch[0]->siz + nw->exist;
                nw = nw->ch[1];
            }
        }return ret;
    }
    int Kth(int k){ // 求出第k大的数
        Node *nw = root;
        while(nw != null){
            if(nw->ch[0]->siz + 1 == k && nw->exist) return nw->key;
            else if(nw->ch[0]->siz >= k) nw = nw->ch[0];
            else k -= nw->ch[0]->siz + nw->exist,nw = nw->ch[1];
        }
    }
    void Erase(int k){ //删除元素k
        Erase(root,Rank(k));
        if(root->siz < alpha*root->cnt) Rebuild(root);
    }
    void Erase_kth(int k){ // 删除第k大的元素
        Erase(root,k);
        if(root->siz < alpha*root->cnt) Rebuild(root);
    }
}Sky;
}}}

const double alpha = 0.75; //重建条件
struct Node{
    Node *ch[2];
    int key,siz,cnt;
    bool exist;
    void update(){
        siz = ch[0]->siz + ch[1]->siz + exist;
        cnt = ch[0]->cnt + ch[1]->cnt + 1;
    }
    bool pa(){
        return (ch[0]->cnt > cnt*alpha + 5) || (ch[1]->cnt > cnt*alpha + 5);
    }
};
struct STree{
    Node mem_poor[maxn];
    Node *tail,*root,*null;
    Node *bc[maxn];
    int bc_top;
    Node* NewNode(int key){
        Node *p = bc_top ? bc[--bc_top] : tail++;
        p->ch[0] = p->ch[1] = null;p->key = key;
        p->siz = p->cnt = 1;p->exist = true;
        return p;
    }
    void Travel(Node *p,vector<Node*>&v){ //重建
        if(p == null) return;
        Travel(p->ch[0],v);
        if(p->exist) v.push_back(p);
        else bc[bc_top++] = p;
        Travel(p->ch[1],v);
    }
    Node* Divide(vector<Node*>&v,int l,int r){ //重建
        if(l >= r) return null;
        int mid = l+r >> 1;
        Node *p = v[mid];
        p->ch[0] = Divide(v,l,mid);
        p->ch[1] = Divide(v,mid+1,r);
        p->update();return p;
    }
    void Rebuild(Node* &p){ //重建函数
        static vector<Node*>v;v.clear();
        Travel(p,v);p = Divide(v,0,v.size());
    }
    Node** Insert(Node* &p,int val){ //在p的子树中插入元素val
        if(p == null){
            p = NewNode(val);
            return &null;
        }else{
            ++(p->siz);++(p->cnt);
            Node **res = Insert(p->ch[val >= p->key],val);
            if(p->pa()) res = &p;
            return res;
        }
    }
    void Erase(Node *p,int id){ //在p的子树中删除元素id
        --(p->siz);
        int x = p->ch[0]->siz + p->exist;
        if(p->exist && id == x){
            p->exist = false;
            return;
        }else{
            if(id <= x) Erase(p->ch[0],id);
            else Erase(p->ch[1],id - x);
        }return;
    }
    void init(){
        tail = mem_poor;
        null = tail++;
        null->ch[0] = null->ch[1] = null;
        null->cnt = null->siz = null->key = 0;
        root = null;bc_top = 0;
    }
    STree(){init();}
    void Insert(int val){ //插入元素val
        Node** p = Insert(root,val);
        if(*p != null) Rebuild(*p);
    }
    int Rank(int val){ // 求出数val在元素中的排名
        Node *nw = root;
        int ret = 1;
        while(nw != null){
            if(nw->key >= val) nw = nw->ch[0];
            else{
                ret += nw->ch[0]->siz + nw->exist;
                nw = nw->ch[1];
            }
        }return ret;
    }
    int Kth(int k){ // 求出第k大的数
        Node *nw = root;
        while(nw != null){
            if(nw->ch[0]->siz + 1 == k && nw->exist) return nw->key;
            else if(nw->ch[0]->siz >= k) nw = nw->ch[0];
            else k -= nw->ch[0]->siz + nw->exist,nw = nw->ch[1];
        }
    }
    void Erase(int k){ //删除元素k
        Erase(root,Rank(k));
        if(root->siz < alpha*root->cnt) Rebuild(root);
    }
    void Erase_kth(int k){ // 删除第k大的元素
        Erase(root,k);
        if(root->siz < alpha*root->cnt) Rebuild(root);
    }
}Sky;