浅谈块状链表

mlvx · 2025-03-01 09:27:55 · 算法·理论

引入

我们都知道，链表可以做到 O(1) 插入和 O(n) 查询，数组可以做到 O(n) 插入和 O(1) 查询。

可否把两个算法有机结合一下呢？

当然是可以的，取块长为 B，则让链表的每个节点都存至多 2B 个数。若里面的数超过 2B，则将其分裂为 2 个有 B 个数的节点。

这样复杂度就是 O(q(B+\dfrac{n}{B})) 的，取 B=O(\sqrt n) 时取得 O(q\sqrt n) 最优。

板子题代码。

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N=1e5+10,L=320,T=320;
struct node{int lst,nxt,len,a[(L<<1)+10];}lt[T<<1];
int n,hd=1,tl=1,len,cnt=1;
pii blk(int pos){
    int now=hd;
    for(;now&&pos>lt[now].len;now=lt[now].nxt)pos-=lt[now].len;
    return{now,pos};
}void spl(int blk){
    ++cnt,lt[cnt].lst=blk,lt[cnt].nxt=lt[blk].nxt,lt[lt[blk].nxt].lst=cnt,lt[blk].nxt=cnt;
    lt[cnt].len=lt[blk].len-len;
    for(int i=len+1;i<=lt[blk].len;i++)lt[cnt].a[i-len]=lt[blk].a[i];
    lt[blk].len=len;
    if(blk==tl)tl=cnt;
}void ins(int blk,int pos,int v){
    for(int i=lt[blk].len;i>=pos;i--)swap(lt[blk].a[i],lt[blk].a[i+1]);
    lt[blk].a[pos]=v,++lt[blk].len;
    if(lt[blk].len>=(len<<1))spl(blk);
}int qry(int pos){pii tmp=blk(pos);return lt[tmp.fi].a[tmp.se];}
int main(){
    cin>>n,len=sqrt(n);
    for(int i=1,x;i<=n;i++)cin>>x,ins(tl,lt[tl].len+1,x);
    for(int op,l,r,c;n--;){
        cin>>op>>l>>r>>c;
        if(op)cout<<qry(r)<<'\n';
        else{pii tmp=blk(l);ins(tmp.fi,tmp.se,r);}
    }return 0;
}

同时也可以用块状链表来做普通平衡树。

只要让这个块状链表有序即可，查排名就用每块最后一个数（即块内最大值），逐块跳，找到块了再到块内跳。

若干小 Trick

区间翻转

左右端点在同块内随便做。

在不同块内的话，就先把左右散块的取出来，一边的翻转过后放到另一边。

然后中间整块先取出来，倒序放回去，并打上懒标记，散块查到或改到的时候再对块内的数组进行修改。

文艺平衡树是可以这么做的。

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N=1e5+10,L=320,T=320;
struct List{int lst,nxt,rev,len,a[(L<<2)+10];}li[T];
int n,q,len,hd=1,tl=1,c1,c2,tmp1[(L<<2)+10],tmp2[(L<<2)+10];stack<int>id;
pii blk(int x){
    for(int i=hd;i;i=li[i].nxt){
        if(x<=li[i].len)return{i,x};
        x-=li[i].len;
    }return{tl,li[tl].len+1};
}void spt(int bl){
    while(li[bl].len>=(len<<1)){
        int x=id.top();id.pop();if(bl==tl)tl=x;
        li[x].nxt=li[bl].nxt,li[li[bl].nxt].lst=x,li[x].lst=bl,li[bl].nxt=x;
        for(int i=li[bl].len-len+1;i<=li[bl].len;i++)li[x].a[++li[x].len]=li[bl].a[i];
        li[bl].len-=len;
    }
}void mrg(int bl){
    if(li[bl].rev)reverse(li[bl].a+1,li[bl].a+li[bl].len+1),li[bl].rev=0;
    if(li[li[bl].nxt].rev)reverse(li[li[bl].nxt].a+1,li[li[bl].nxt].a+li[li[bl].nxt].len+1),li[li[bl].nxt].rev=0;
    for(int i=li[bl].len+1;i<=li[bl].len+li[li[bl].nxt].len;i++)li[bl].a[i]=li[li[bl].nxt].a[i-li[bl].len];
    li[bl].len+=li[li[bl].nxt].len,li[li[bl].nxt].len=0,id.push(li[bl].nxt),li[bl].nxt=li[li[bl].nxt].nxt,li[li[bl].nxt].lst=bl;
}
void ins(int bl,int x,int v){
    for(int i=li[bl].len;i>=x;i--)swap(li[bl].a[i],li[bl].a[i+1]);
    li[bl].a[x]=v;if(++li[bl].len>=len<<1)spt(bl);
}void revs(int bll,int xl,int blr,int xr){
    if(bll==blr){
        if(li[bll].rev)reverse(li[bll].a+1,li[bll].a+li[bll].len+1),li[bll].rev=0;
        reverse(li[bll].a+xl,li[bll].a+xr+1);
    }else{
        if(li[bll].rev)reverse(li[bll].a+1,li[bll].a+li[bll].len+1),li[bll].rev=0;
        if(li[blr].rev)reverse(li[blr].a+1,li[blr].a+li[blr].len+1),li[blr].rev=0;
        c1=c2=0;
        for(int i=xl;i<=li[bll].len;i++)tmp1[++c1]=li[bll].a[i];
        for(int i=1;i<=xr;i++)tmp2[++c2]=li[blr].a[i];
        reverse(tmp1+1,tmp1+c1+1),reverse(tmp2+1,tmp2+c2+1),li[bll].len=xl+c2-1;
        for(int i=xl;i<=li[bll].len;i++)li[bll].a[i]=tmp2[i-xl+1];
        if(xr<c1)for(int i=li[blr].len;i>xr;i--)swap(li[blr].a[i],li[blr].a[i-xr+c1]);
        if(xr>c1)for(int i=xr+1;i<=li[blr].len;i++)swap(li[blr].a[i],li[blr].a[i-xr+c1]);
        li[blr].len+=c1-xr;
        for(int i=1;i<=c1;i++)li[blr].a[i]=tmp1[i];
        c1=0;
        for(int i=li[blr].lst;i!=bll;i=li[i].lst)tmp1[++c1]=i,li[i].rev^=1;
        for(int lst=bll,i=1;i<=c1;i++)li[lst].nxt=tmp1[i],li[tmp1[i]].lst=lst,lst=tmp1[i];
        li[blr].lst=c1?tmp1[c1]:bll,li[c1?tmp1[c1]:bll].nxt=blr,spt(bll),spt(blr);
    }
}int main(){
    cin>>n>>q,len=sqrt(n);
    for(int i=2;i<=(n-1)/len+1;i++)id.push(i);
    for(int i=1;i<=n;i++)ins(tl,li[tl].len+1,i);
    for(int l,r;q--;){
        cin>>l>>r;pii tmp1=blk(l),tmp2=blk(r);
        revs(tmp1.fi,tmp1.se,tmp2.fi,tmp2.se);
        for(int i=hd;i;i=li[i].nxt)if(li[i].nxt&&li[i].len+li[li[i].nxt].len<len<<1)mrg(i);
    }for(int i=hd;i;i=li[i].nxt){
        if(li[i].rev)reverse(li[i].a+1,li[i].a+li[i].len+1);
        for(int j=1;j<=li[i].len;j++)cout<<li[i].a[j]<<' ';
    }return 0;
}

查找某数出现位置 / 区间某数出现次数

这个题是排列，因此只需要记录每块内是否有 x，若块内有，则暴力在块内查找。

记录每块内是否有 x 开个 bitset 即可，空间 O(\dfrac{n\sqrt n}{w})。

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define piii pair<pii,int>
#define fi first
#define se second
const int N=8e4+10,L=290,T=290;
struct List{int nxt,len,a[(L<<1)+10];bitset<N>vis;}li[T<<1];
int n,len,q,hd=1,tl=1,cnt=1;char op[10];
pii blk(int x){
    for(int i=hd;i;i=li[i].nxt){if(x<=li[i].len)return{i,x};x-=li[i].len;}
    return{tl,li[tl].len+1};
}void spt(int bl){
    ++cnt;if(bl==tl)tl=cnt;li[cnt].nxt=li[bl].nxt,li[bl].nxt=cnt;
    for(int i=len+1;i<=li[bl].len;i++)li[cnt].a[++li[cnt].len]=li[bl].a[i],li[bl].vis[li[bl].a[i]]=0,li[cnt].vis[li[bl].a[i]]=1;
    li[bl].len=len;
}void ins(int bl,int x,int v){
    for(int i=li[bl].len;i>=x;i--)swap(li[bl].a[i],li[bl].a[i+1]);
    li[bl].a[x]=v,li[bl].vis[v]=1;if(++li[bl].len>=len<<1)spt(bl);
}void del(int bl,int x){
    for(int i=x+1;i<=li[bl].len;i++)swap(li[bl].a[i-1],li[bl].a[i]);
    li[bl].vis[li[bl].a[li[bl].len--]]=0;
}piii find(int x,int s=0){for(int i=hd,j;i;s+=li[i].len,i=li[i].nxt)if(li[i].vis[x])for(j=1;j<=li[i].len;s++,j++)if(li[i].a[j]==x)return{{i,j},s+1};}
int main(){
    cin>>n>>q,len=sqrt(n);
    for(int i=1,x;i<=n;i++)cin>>x,ins(tl,li[tl].len+1,x);
    for(int x,y;q--;){
        scanf(" %s %d",op,&x);
        if(op[0]=='T'){piii tmp=find(x);del(tmp.fi.fi,tmp.fi.se),ins(1,1,x);}
        else if(op[0]=='B'){piii tmp=find(x);del(tmp.fi.fi,tmp.fi.se),ins(tl,li[tl].len+1,x);}
        else if(op[0]=='I'){scanf("%d",&y);piii tmp=find(x);del(tmp.fi.fi,tmp.fi.se);pii _=blk(tmp.se+y);ins(_.fi,_.se,x);}
        else if(op[0]=='A'){piii tmp=find(x);cout<<tmp.se-1<<'\n';}
        else{pii tmp=blk(x);cout<<li[tmp.fi].a[tmp.se]<<'\n';}
    }return 0;
}

区间某数出现次数的话就记录每个块的 cnt，cnt_x 表示当前块内 x 的出现次数，空间 O(n\sqrt n)。

没见过这样的题，因此没有代码实现。

区间 k 大

相信大家都会静态区间 k 大的单根做法，即序列分块加值域分块。

而把这个做法搬到块状链表上也同样可行。

每个块内 cnt1_x 表示第一块到当前块 x 的出现次数，cnt2_x 表示第一块到当前块有多少个数位于第 x 个值域块中。

分裂就直接暴力更新 cnt1 和 cnt2。

查询时左右端点在同块内，把东西都塞进桶中即可。

否则先把散块塞进桶中，整块的直接前缀和相减。

然后先跳值域块，找到值域块再在该值域块内找。

时间复杂度 O(n(\sqrt n+\sqrt V))，空间复杂度 O(V\sqrt n)。

这个题就是这个做法。

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N=7e4+10,V=7e4+10,L=270,T=270,VT=270;
struct List{int nxt,len,a[(L<<1)+10],cnt1[V],cnt2[VT];}li[T];
int n,q,len,vlen,vtot,hd=1,tl=1,blv[V],t[V],tt[VT],lev[VT],riv[VT];char op;queue<int>id;
inline pii blk(int x){
    for(int i=hd;i;x-=li[i].len,i=li[i].nxt)if(x<=li[i].len)return{i,x};
    return{tl,li[tl].len+1};
}inline void spt(int bl){
    int x=id.front();id.pop(),li[x].nxt=li[bl].nxt,li[bl].nxt=x;if(bl==tl)tl=x;
    memcpy(li[x].cnt1,li[bl].cnt1,sizeof li[x].cnt1),memcpy(li[x].cnt2,li[bl].cnt2,sizeof li[x].cnt2);
    for(int i=len+1;i<=li[bl].len;i++)li[x].a[++li[x].len]=li[bl].a[i],--li[bl].cnt1[li[bl].a[i]],--li[bl].cnt2[blv[li[bl].a[i]]];
    li[bl].len=len;
}inline void mrg(int bl){
    memcpy(li[bl].cnt1,li[li[bl].nxt].cnt1,sizeof li[bl].cnt1),memcpy(li[bl].cnt2,li[li[bl].nxt].cnt2,sizeof li[bl].cnt2);
    for(int i=1;i<=li[li[bl].nxt].len;i++)li[bl].a[++li[bl].len]=li[li[bl].nxt].a[i];
    li[li[bl].nxt].len=0,id.push(li[bl].nxt),li[bl].nxt=li[li[bl].nxt].nxt;
}inline void ins(int bl,int x,int v){
    for(int i=li[bl].len;i>=x;i--)swap(li[bl].a[i],li[bl].a[i+1]);
    li[bl].a[x]=v;
    for(int i=bl;i;i=li[i].nxt)++li[i].cnt1[v],++li[i].cnt2[blv[v]];
    if(++li[bl].len>=len<<1)spt(bl);
}inline void del(int bl,int x){
    for(int i=bl;i;i=li[i].nxt)--li[i].cnt1[li[bl].a[x]],--li[i].cnt2[blv[li[bl].a[x]]];
    for(int i=x+1;i<=li[bl].len;i++)swap(li[bl].a[i-1],li[bl].a[i]);
    --li[bl].len;
}inline int qkth(int bll,int xl,int blr,int xr,int k){
    int ret;
    if(bll==blr){
        for(int i=xl;i<=xr;i++)++t[li[bll].a[i]],++tt[blv[li[bll].a[i]]];
        int tmp=0,bl;
        for(int i=1;i<=vtot;i++){
            tmp+=tt[i];
            if(tmp>=k){tmp-=tt[i],bl=i;break;}
        }for(int i=lev[bl];i<=riv[bl];i++){
            tmp+=t[i];
            if(tmp>=k){ret=i;break;}
        }for(int i=xl;i<=xr;i++)--t[li[bll].a[i]],--tt[blv[li[bll].a[i]]];
    }else{
        for(int i=xl;i<=li[bll].len;i++)++t[li[bll].a[i]],++tt[blv[li[bll].a[i]]];
        for(int i=1;i<=xr;i++)++t[li[blr].a[i]],++tt[blv[li[blr].a[i]]];
        int tmp=0,blrlst,bl;
        for(int i=bll;i;i=li[i].nxt)if(li[i].nxt==blr){blrlst=i;break;}
        for(int i=1;i<=vtot;i++){
            tmp+=tt[i]+li[blrlst].cnt2[i]-li[bll].cnt2[i];
            if(tmp>=k){tmp-=tt[i]+li[blrlst].cnt2[i]-li[bll].cnt2[i],bl=i;break;}
        }for(int i=lev[bl];i<=riv[bl];i++){
            tmp+=t[i]+li[blrlst].cnt1[i]-li[bll].cnt1[i];
            if(tmp>=k){ret=i;break;}
        }for(int i=xl;i<=li[bll].len;i++)--t[li[bll].a[i]],--tt[blv[li[bll].a[i]]];
        for(int i=1;i<=xr;i++)--t[li[blr].a[i]],--tt[blv[li[blr].a[i]]];
    }return ret;
}int main(){
    cin>>n,len=264,vlen=264,vtot=(V-10)/vlen+1;
    for(int i=1;i<=vtot;i++)lev[i]=riv[i-1]+1,riv[i]=riv[i-1]+vlen;
    riv[vtot]=V-9;
    for(int i=1;i<=V-9;i++)blv[i]=(i-1)/vlen+1;
    for(int i=2;i<=(N-11)/len+1;i++)id.push(i);
    for(int i=1,x;i<=n;i++)cin>>x,ins(tl,li[tl].len+1,x+1);
    cin>>q;
    for(int lst=0,x,y,z;q--;){
        cin>>op>>x>>y,x^=lst,y^=lst;
        if(op=='Q'){cin>>z,z^=lst;pii tmpl=blk(x),tmpr=blk(y);cout<<(lst=qkth(tmpl.fi,tmpl.se,tmpr.fi,tmpr.se,z)-1)<<'\n';}
        else if(op=='M'){pii tmp=blk(x);del(tmp.fi,tmp.se),ins(tmp.fi,tmp.se,y+1);}
        else{pii tmp=blk(x);ins(tmp.fi,tmp.se,y+1);}
        for(int i=hd;i;i=li[i].nxt)if(li[i].nxt&&li[i].len+li[li[i].nxt].len<len<<1)mrg(i);
    }return 0;
}

小优化

每次修改完后扫一遍块，若相邻两块的长度和 <2B，则可以进行合并的操作。

合并完之后块的下标就有一个没用了，会有空间浪费。

这时候我们可以写个内存池，表示那些下标现在还可以使用，合并完之后没用的下标就丢进去。

这个优化前面的代码里有，可以去参考一下如何实现。

关于块状链表的可持久化

貌似是可以可持久化的，对每个信息都可持久化，把存数的那个二维数组压成一维就好搞了。

这个题由于单次操作最多使 O(\sqrt n) 个信息改变，故时空复杂度 O(q\sqrt n\log n)，显然是过不去的，所以没有代码实现。

什么垃圾东西。

例题

P2042：很麻烦，要打两个标记，还要维护最大子段和，码量超大。