z3475 的博客

题解 P3960 【列队】

我的思路和1L那位用Splay一样,只不过楼上用的是Splay或者FHQtrep维护的,我用的是替罪羊树

事实上所有平衡操作不依赖比较的平衡树都可以维护区间,只需要稍稍改造以下就好了

然后说说我用替罪羊树在写此题时发现了一个诡异的事情

当替罪羊的alpha取值为0.9时跑的最快

qwq0.9,这说明建出来的树可能极度的不平衡,但是却跑的最快??

反正替罪羊树维护平很都很玄学,alpha玄学也挺...挺正常的(求Dalao证明)

#include <bits/stdc++.h>

using namespace std;
#define ull long long
#define alpha (double)0.9
#define lson ch[0]
#define rson ch[1]
template<class T,class iT=long long>
struct node{
    #define gl(a) (lson==nullptr?0:lson->a)
    #define gr(a) (rson==nullptr?0:rson->a)
    node *ch[2];
    iT cover,many,size;//下属(包括自己)有效节点数量 & ~总数量 
    T val;
    inline void maintain(){//维护
        cover=gl(cover)+gr(cover)+1;
        size=gl(size)+gr(size)+many;
    }
    inline bool isBad(){//是不是替罪羊 
        return max(gl(cover),gr(cover))>cover*alpha;
    }
    node(){}
    node(T _val,iT _many){
        ch[0]=ch[1]=nullptr;
        many=_many;
        val=_val;
        maintain();
    }
};
static node<ull> mem_pool[5000000];
static node<ull> *del_pool[5000000];
static node<ull> *memi=mem_pool;
static node<ull> **deli=del_pool;
node<ull>* add(node<ull> a){
    if (deli!=del_pool) return &(**--deli=a);
    return &(*memi++=a);
}
void del(node<ull> *a){
    *deli++=a;
}
#define gl(a,n) (n==nullptr||n->lson==nullptr?0:n->lson->a)
#define gr(a,n) (n==nullptr||n->rson==nullptr?0:n->rson->a)
#define gt(a,n) (n==nullptr?0:n->a)
template<class T,class iT=long long>
struct STree{
    node<T> *root;iT maxCover;
    STree(){root=nullptr;maxCover=0;}
    inline void toArry(register node<T> *p,register vector<node<T>*> &v){//拍扁并回收 
        if (p==nullptr) return ;
        toArry(p->lson,v);
        if (p->many) v.push_back(p);
        toArry(p->rson,v);
        if (!p->many) del(p);
    }
    inline node<T>* toTree(register vector<node<T>*> &v,register ull l,register ull r){//建树 
        if (l>=r) return nullptr;
        register ull mid=(l+r)>>1;
        register node<T> *p=v[mid];
        p->lson=toTree(v,l,mid);
        p->rson=toTree(v,mid+1,r);
        p->maintain();
        return p;
    }

    inline void rebuild(register node<T> *&p){          //把前面两个函数怼在一起就是重建了 
        if (p!=nullptr){                    //因为重建后可能当前节点会变,所以要用*& 
            vector<node<T>*> v;
            toArry(p,v);
            p=toTree(v,0,v.size());
            maxCover=gt(cover,p);
        }
    }

    node<T> **need,*now;//need表示需要重建的节点关系,now表示插入后的节点 
    inline void falseInsert(register node<T> *&p,register node<T> *todo,register iT kth){//递归插入 
        if (p==nullptr){
            now=p=todo;
            need=nullptr;
        }else{
            register ull lsize=gl(size,p);
            register ull all=lsize+p->many;
            if (kth>=all) falseInsert(p->rson,todo,kth-all);
            else falseInsert(p->lson,todo,kth);
            p->cover++;p->size+=todo->many;
            if (p->isBad()) need=&p;
        }
    }

    inline node<T>* insert(register node<T> to,register iT kth){//对递归插入的简单封装
        register node<T> *todo=add(to);
        falseInsert(root,todo,kth);
        if (need!=nullptr) rebuild(*need);
        maxCover=max(maxCover,gt(cover,root));
        return now;
    }   

    inline void falseErase(register node<T> *p,register iT k){//同上 
        register ull lsize=gl(size,p);
        register ull all=lsize+p->many;
        if (p!=nullptr){
            if(lsize>=k) falseErase(p->lson,k); else
            if(p->many&&all>=k) now=p;
            else falseErase(p->rson,k-all);
            p->size-=gt(many,now);
        }
    }

    inline void erase(register iT k){//对递归删除的简单封装
        falseErase(root,k);
        now->many=0;
        if (root!=nullptr&&root->cover<=alpha*maxCover) rebuild(root),maxCover=gt(cover,root);
    }

    inline iT kth(register iT k){//求第k大数 返回[a,b],a+1 
        register node<T> *p=root;
        while (p!=nullptr){
            ull lsize=gl(size,p);
            ull all=lsize+p->many;
            if(lsize>=k) p=p->lson; else
            if(p->many&&all>=k) break;
            else k-=all,p=p->rson;
        }
        now=p;
        return k-gl(size,p);
    }
};
STree<ull> l[300004],e;
ull gi(){
    register ull i=0;register char c;
    while (!(isdigit(c=getchar())));
    do i=c-'0'+(i<<3)+(i<<1); while ((isdigit(c=getchar())));
    return i;
}
void put(long long a,char split='\n'){
    char p[20];int i=0;
    while (a) p[i++]=a%10+'0',a/=10;
    while (i) putchar(p[--i]);
    putchar(split);
}
ull n,m,q;
int main(){
    n=gi();m=gi();q=gi();
    if (m!=1) for (register ull i=1;i<=n;i++) l[i].insert(node<ull>((i-1)*m+1,m-1),1);//初始化每行 
    for (register ull i=1;i<=n;i++) e.insert(node<ull>(i*m,1),gt(size,e.root)+1);//初始化最后一列 
    for (register ull i=1;i<=q;i++){
        ull x,y;
        x=gi();y=gi();
        if (y==m){
            e.kth(x);
            register ull a=e.now->val;
            put(a);
            e.erase(x);
            e.insert(node<ull>(a,1),e.root->size+1);
        }else{
            register ull py=l[x].kth(y);
            register ull dv=l[x].now->val;
            register ull dm=l[x].now->many;
            //每行被分成了三个区间 
            //[dv,dv+py-1)
            //[dv+py-1]->要求的值 
            //[dv+py,dv+dm)
            put(dv+py-1);
            l[x].erase(y);
            if (dm-py>0) l[x].insert(node<ull>(dv+py,dm-py),y-py);
            if (py-1>0) l[x].insert(node<ull>(dv,py-1),y-py);
            e.kth(x);register ull d1=e.now->val;
            e.erase(x);
            l[x].insert(node<ull>(d1,1),l[x].root->size+1);
            e.insert(node<ull>(dv+py-1,1),e.root->size+1);
        }
    }
}

2018-08-23 11:31:21 in 题解