题解：P13981 数列分块入门 6

· · 题解

块状链表

loj 6282 / luogu P13981。

其实核心代码并不长，但值得自行实现。

题意

维护以下操作：

块状链表简介

链表可以快速维护插入元素操作，但随机访问的时间复杂度为线性；数组的随机访问快速，但插入元素的时间复杂度为线性。

尝试把这两个数据存储结构结合，如果在 \sqrt n 级别链表的节点内套入 <2\sqrt n 个元素的数组，这个就叫块状链表。

这样，我们如果需要随机访问，可以先在外部链表内，查找这个元素对应在哪个节点内，然后在这个节点的数组中快速访问这个值；如果需要插入元素，可以在找到对应链表节点之后，在节点内数组中暴力插入。

但是，维护插入元素时，一个链表节点中包含的元素可能 \geq2\sqrt n。具体地，如果在同一个链表节点插入 q 次元素，那么这个节点的大小可以达到 \sqrt n+q，由于在数组内插入一个元素的时间可以达到线性，故时间复杂度可以达到 \Theta(q^2) 级别，显然是会超时的。此时需要在元素数量达到 2\sqrt n 的时候进行一个节点分裂操作，将链表节点切成两份。这保证了单次操作的时间复杂度为 \Theta(\sqrt n) 级别。

查询从左往右某个下标的元素，只需要记录每个链表节点包含元素个数，然后遍历即可。

具体细节

链表节点内部元素数组实现

以下是手写 vector 的实现，你也可以选择直接使用 std::vector。

    struct Vector{
        int a[SN<<1],tip;
        void push_back(int x){//在最后插入一个元素
            a[++tip]=x;
        }
        void insert(int x,int t){//在中间插入一个元素，复杂度根号
            for (int i=tip;i>=t;i--)
                a[i+1]=a[i];
            tip++,a[t]=x;
        }
        void pop_back(){//弹出最后一个元素
            tip--;
        }
    };

单个节点的内部信息

需要记录某个节点中，其元素在原数组内对应的连续区间。因为是链表，故需要维护每个节点的前驱后继。

    struct Block{
        int l,r;//节点内部元素对应在原数组的区间
          Vector e;//内部元素
    };
    struct List{
        Block ths;
        int lst,nxt;//节点在链表内的前驱后继
    }b[SN<<1];

建立块状链表

初始情况下，记录信息是容易的。

    void build(){
        val=sqrt(n);//块长
        for (int i=1;i<=n;i++){
            int bnow=(i-1)/val+1,blst=(i-2)/val+1;
            if (i==1||bnow!=blst){//判断是否需要建立一个新的节点
                if (i>1){
                    b[BlockCnt].nxt=BlockCnt+1;
                    b[BlockCnt].ths.r=i-1;//记录对应信息
                }
                BlockCnt++,b[BlockCnt].lst=BlockCnt-1;
                b[BlockCnt].ths.l=i;//记录对应信息
            }
            b[BlockCnt].ths.e.push_back(a[i]);//在对应节点中存入元素
        }
        b[1].ths.l=1,b[BlockCnt].ths.r=n;
        b[1].lst=-1,b[BlockCnt].nxt=-1;//链表两端位置的对应前驱/后继不存在，为了方便，设为 -1
    }

分裂一个链表上的节点

如果一个链表上的节点，其对应的存储元素个数大于等于 2\sqrt n，需要将其分裂为两个节点，以保证复杂度。

    void spilt(int id){
        if (b[id].ths.r-b[id].ths.l+1<2*val)//不满足条件时自动忽略操作
            return;
        BlockCnt++;//新建节点
        for (int i=val+1;i<=b[id].ths.r-b[id].ths.l+1;i++)
            b[BlockCnt].ths.e.push_back(b[id].ths.e.a[i]);
        for (int i=val+1;i<=b[id].ths.r-b[id].ths.l+1;i++)
            b[id].ths.e.pop_back();//转移元素
        b[BlockCnt].ths.l=b[id].ths.l+val,b[BlockCnt].ths.r=b[id].ths.r;
        b[id].ths.r=b[id].ths.l+val-1;//更改对应区间
        b[BlockCnt].nxt=b[id].nxt,b[id].nxt=BlockCnt;
        b[BlockCnt].lst=id,b[b[BlockCnt].nxt].lst=BlockCnt;//更改相邻节点的前驱、后继
    }

操作 1：插入元素

接下来的两个操作的实现不难。

遍历链表找到对应的节点之后，直接在节点的元素 vector 内插入元素，如果存储元素个数达到 2\sqrt n 就直接分裂即可。

    void insert(int x,int k){
        int id=0,tx=1;
        while (tx!=-1&&!id){//找到对应节点
            if (b[tx].ths.r>=x) id=tx;
            tx=b[tx].nxt;
        }
        b[id].ths.e.insert(k,x-b[id].ths.l+1);
        b[id].ths.r++,tx=b[id].nxt;//插入元素，更改信息
        while (tx!=-1){//需要更改这以后的节点对应的区间
            b[tx].ths.l++,b[tx].ths.r++;
            tx=b[tx].nxt;
        }
        spilt(id);//注意，这里如果不满足区间长度的条件，分裂操作不会执行
    }

操作 2：查找元素

遍历链表找到节点，在这个节点的 vector 里找元素即可。

    int query(int x){
        int id=0,tx=1;
        while (tx!=-1&&!id){//查找节点
            if (b[tx].ths.r>=x) id=tx;
            tx=b[tx].nxt;
        }
        return b[id].ths.e.a[x-b[id].ths.l+1];//直接通过查找下标的方式，查询对应元素
    }

完整代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
inline int read(){
    int res=0,f=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {res=res*10+(c-'0');c=getchar();}
    return res*f;
}
const int N=3e5+5,SN=1e3+5;
int n,a[N];
struct BlockList{
    struct Vector{
        int a[SN<<1],tip;
        void push_back(int x){
            a[++tip]=x;
        }
        void insert(int x,int t){
            for (int i=tip;i>=t;i--)
                a[i+1]=a[i];
            tip++,a[t]=x;
        }
        void pop_back(){
            tip--;
        }
    };
    struct Block{
        int l,r;
        Vector e;
    };
    struct List{
        Block ths;
        int lst,nxt;
    }b[SN<<1];
    int BlockCnt,val;
    void build(){
        val=sqrt(n);
        for (int i=1;i<=n;i++){
            int bnow=(i-1)/val+1,blst=(i-2)/val+1;
            if (i==1||bnow!=blst){
                if (i>1){
                    b[BlockCnt].nxt=BlockCnt+1;
                    b[BlockCnt].ths.r=i-1;
                }
                BlockCnt++,b[BlockCnt].lst=BlockCnt-1;
                b[BlockCnt].ths.l=i;
            }
            b[BlockCnt].ths.e.push_back(a[i]);
        }
        b[1].ths.l=1,b[BlockCnt].ths.r=n;
        b[1].lst=-1,b[BlockCnt].nxt=-1;
    }
    void spilt(int id){
        if (b[id].ths.r-b[id].ths.l+1<2*val)
            return;
        BlockCnt++;
        for (int i=val+1;i<=b[id].ths.r-b[id].ths.l+1;i++)
            b[BlockCnt].ths.e.push_back(b[id].ths.e.a[i]);
        for (int i=val+1;i<=b[id].ths.r-b[id].ths.l+1;i++)
            b[id].ths.e.pop_back();
        b[BlockCnt].ths.l=b[id].ths.l+val,b[BlockCnt].ths.r=b[id].ths.r;
        b[id].ths.r=b[id].ths.l+val-1;
        b[BlockCnt].nxt=b[id].nxt,b[id].nxt=BlockCnt;
        b[BlockCnt].lst=id,b[b[BlockCnt].nxt].lst=BlockCnt;
    }
    void insert(int x,int k){
        int id=0,tx=1;
        while (tx!=-1&&!id){
            if (b[tx].ths.r>=x) id=tx;
            tx=b[tx].nxt;
        }
        b[id].ths.e.insert(k,x-b[id].ths.l+1);
        b[id].ths.r++,tx=b[id].nxt;
        while (tx!=-1){
            b[tx].ths.l++,b[tx].ths.r++;
            tx=b[tx].nxt;
        }
        spilt(id);
    }
    int query(int x){
        int id=0,tx=1;
        while (tx!=-1&&!id){
            if (b[tx].ths.r>=x) id=tx;
            tx=b[tx].nxt;
        }
        return b[id].ths.e.a[x-b[id].ths.l+1];
    }
}book;
signed main(){
    n=read();
    for (int i=1;i<=n;i++)
        a[i]=read();
    book.build();
    for (int i=1;i<=n;i++){
        int op=read(),l,r;
        if (op==0) l=read(),r=read(),book.insert(l,r);
        else if (op==1) r=read(),cout<<book.query(r)<<'\n';、
    }
    return 0;
}