题解 P3960 【列队】

我的思路和1L那位用Splay一样，只不过楼上用的是Splay或者FHQtrep维护的，我用的是替罪羊树 事实上所有平衡操作不依赖比较的平衡树都可以维护区间，只需要稍稍改造以下就好了 然后说说我用替罪羊树在写此题时发现了一个诡异的事情 当替罪羊的alpha取值为**0.9**时跑的最快 0.9,这说明建出来的树可能极度的不平衡,但是却跑的最快?? 反正替罪羊树维护平很都很玄学,alpha玄学也挺...挺正常的(求Dalao证明) ```cpp #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); } } } ```