块状链表

luckydrawbox · 2021-09-05 15:45:23 · 个人记录

使用前，请根据自己需要更改基本数据类型：

#define B_L_T int

以上实现了一个以 \text{int} 为基本数据类型的块状链表定义。

为了实现输出元素值的操作，使用前请根据需要更改输出方式 \text{put}(val) 操作：

void put(B_L_T val){
    printf("%d ",val);
}

变量

使用前要设定好 max\_len。

已经实现的操作

可用于扩展的基本操作

块状链表灵活多变，可以使用以下基本操作扩展到其他操作。

#define B_L_T int
struct Block_List{
    int tot,nc[N],size,len;
    double max_len;
    struct Block{
        int head,next;
        int len;
        B_L_T b[2*N];
    }a[N],e;
    B_L_T add[M];
    Block_List(){
        tot=0;size=0;
        e.head=e.next=0;
        e.len=0;
        max_len=2;
        for(int i=1;i<N;i++)
            nc[i]=i;
    }
    int build(int p){
        int np=nc[++tot];
        a[np]=e;
        a[np].head=p;
        a[np].next=a[p].next;
        a[a[p].next].head=np;
        a[p].next=np;
        return np;
    }
    void del(int p){
        nc[tot--]=p;
        a[a[p].head].next=a[p].next;
        a[a[p].next].head=a[p].head;
    }
    int get(int &p){
        int kp=a[0].next;
        for(;kp;kp=a[kp].next)
            if(a[kp].len<p)
                p-=a[kp].len;
            else
                break;
        p--;
        return kp;
    }
    void split(int p,int pos){
        int np=build(p);
        a[np].len=pos;
        a[p].len-=a[np].len;
        for(int i=0;i<a[np].len;i++)
            a[np].b[i]=a[p].b[i+a[p].len];
    }
    void merge(int p){
        for(int i=0;i<a[a[p].next].len;i++)
            a[p].b[a[p].len+i]=a[a[p].next].b[i];
        a[p].len+=a[a[p].next].len;
        del(a[p].next);
    }
    void insert(int p,int n){
        n--; 
        if(p>size)
            return;
        size+=n+1;
        len=sqrt(size);
        int kp=get(p),nkp;
        if(p^(a[kp].len-1))
            split(kp,p);
        nkp=kp;
        for(int i=0;i<n/len;i++){
            nkp=build(nkp);
            a[nkp].len=len;
            for(int j=0;j<a[nkp].len;j++)
                a[nkp].b[j]=add[j+i*len];
        }
        nkp=build(nkp);
        a[nkp].len=n-n/len*len+1;
        for(int i=n/len*len;i<=n;i++)
            a[nkp].b[i-n/len*len]=add[i];
        for(;nkp&&(!kp||nkp!=a[kp].head);nkp=a[nkp].head){
            if(a[nkp].next&&a[nkp].len+a[a[nkp].next].len<max_len*len)
                merge(nkp);
        }
    }
    void remove(int p,int n){
        if(p>size)
            return;
        int l=p,r=min(p+n-1,size);
        size-=r-l+1;
        len=sqrt(size);
        int kl=get(l),kr=get(r);
        if(l){
            split(kl,l-1);
            kl=a[kl].next;
        }
        if(r^(a[kr].len-1))
            split(kr,r);
        for(int k=kl;k^a[kr].next;k=a[k].next)
            del(k);
        if(a[kl].head&&a[kr].next&&a[a[kl].head].len+a[a[kr].next].len<max_len*len)
            merge(a[kl].head);
    }
    void put(B_L_T val){
        printf("%d ",val);
    }
    void write(int l,int r){
        int lsl=l,lsr=r;
        int kl=get(l),kr=get(r);
        if(kl==kr){
            for(int i=l;i<=r;i++)
                put(a[kl].b[i]);
            return;
        }
        write(lsl,lsl+a[kl].len-1-l);
        for(int k=a[kl].next;k^kr;k=a[k].next)  
            for(int i=0;i<a[k].len;i++)
                put(a[k].b[i]);
        write(lsr-r,lsr);
    }
}K;