fhqtreap

这个神仙级nb的数据结构得名于神仙范皓强,既有treap的易写易懂,也有splay般易于区间处理的能力.

列队

https://www.luogu.com.cn/problem/P3960
题意:一个nm的矩阵,每次取出一个指定位置的数,求出这个数的编号,并把矩阵里的数先向左补齐再想上补齐,最后把取出的数塞到右下角.其中$n,m,q\in(1,3e5)$
考虑每次更改的部分,只有当前的行和最后一列会有更改.于是对每一行和最后一列建立平衡树维护矩阵.但是这样做的空间复杂度是$O(nm)$,无法承受.
由于大部分数都不会被更改,每个点都去维护的话实际上浪费了大量空间.那么就考虑去合并这些不会被更改的点,更好的做法就是直接维护区间,有分裂的需求时再动态开点.一开始对每行插入$(1,m-1)$的区间,对末尾列直接插入每一个数.在split时开新点分割区间.
此处的treap按排名分裂.需要注意fhqtreap的合并顺序,以及新开的点与原树的相对位置.这个细节废了我一个下午.

int mer(int x,int y){
    if(!x||!y) return x+y;
    if(rd[x]>=rd[y])return rs(x)=mer(rs(x),y),upd(x),x;
    else return ls(y)=mer(x,ls(y)),upd(y),y; 
}
void splp(int p,ll k){
    if(k>=len(p)) return ;
    int x=alc(L[p]+k,R[p]);
    R[p]=L[x]-1,rs(p)=mer(x,rs(p)),upd(p);
}
void spl(int p,int &x,int &y,ll v){
    if(!p) return x=y=0,void();
    if(sz[ls(p)]>=v) y=p,spl(ls(p),x,ls(p),v);
    else splp(p,v-sz[ls(p)]),x=p,spl(rs(p),rs(p),y,v-sz[ls(p)]-len(p));
    upd(p);
}