块状链表小结(NOI2003 Editor)


学过数组和链表的同学肯定知道:

数组支持O(1)访问,而插入则需要O(N)
链表支持O(1)插入,二访问却需要O(N)

那么问题来了:
如果有道题,需要你动态插入并随时访问,同时还卡你空间,怎么办?
例题:[NOI2003]Editor
题目要求你的算法/数据结构资瓷插入区间,删除区间,访问区间,空间也卡到了162MB。
于是。怎么写?
说rope的出门右转,rope是C++11的,CCF系列赛事一般不支持哟
而且比块状链表慢!
准备瞎扯:
块状链表是数组与链表的结合体,链表上的每个点都是一个数组集合
非常nice地资瓷的查询和插入以及删除。空间小,速度快,值得你拥有。


首先,第一个操作-定位:

你总需要知道你要找的东西在哪一个块里吧。

大概类似Splay找第k大?
假设你要找下标p所在的块,因为你知道每个块的大小,你就从头扫到尾,每扫一个块都减去那个块的大小。
直到减为负数。(不是很会表达,大概懂意思就好辣!!)


第二个操作-维护块状链表形态:
为了保证效率,块状链表的形态是需要维护的,不维护形态的话可以随便卡成链表(就是每个块的大小为1)。
做法大概就是:
你从头扫到尾,若发现某个块比较小,比如大小小于的块,你就可以把它和后面那个块合并,合并的条件有很多种版本,一般都是在区间[\sqrt{N},2\cdot\sqrt{N}]内的。
合并的话也不难:
直接把一个块copy到另外一个块并删除原块,是不是肥肠简单。


分裂:
分裂比较简单。假设你要分裂第p个块,你就需要先新建一个空块插入到第p个块与第p+1个块中间。
然后直接把要分裂的后面一部分剪切过去


插入:
假设你要插入一个字符串str到整个字串的第p个字符后,你需要先得到第p个字符在哪个块。
再以字符p的右侧为分界线把这个块给切成两半,最后直接把str接到以p为尾的块后面即可。


删除:
假设你要删除从下标p开始长度为l的字符串。
你可以非常自然地想到先找到下标p和下标p+l分别在哪个块。
如果你学过分块,你也可以非常自然地想到如果下标p到下标p+l的区间中有整块可以直接删除整块。
这些想法都是非常正确的!
对于不是整块,你也可以非常自然地想到——把整块中我们要删除的那一部分分裂出来再删除。


这样子你就在学会块状链表的同时A了这道NOI题(其实这就是块状链表模板题)。
下面贴上此题代码,请在代码内自行寻找块状链表模板。

#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define reg register
#define ll long long
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define MAXL (2*1024*1024+10)
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
#define swap(a,b) ((a)==(b)?(a)=(b):((a)^=(b)^=(a)^=(b)))
using namespace std;
template<typename T> inline void read(T&x){T f=1;x=0;char c;
    for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
    for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
    int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
char str[MAXL];
struct BlockList{
    #define MAXBLOCK 1500
    #define BLOCKSIZE 1500
    char data[MAXBLOCK][BLOCKSIZE];
    int freelist[MAXBLOCK],sz[MAXBLOCK],nxt[MAXBLOCK],freepos;
    inline void Clear(){
        for(int i=1; i<=MAXBLOCK-1; ++i) freelist[i]=i;
        freepos=1;nxt[0]=-1;sz[0]=0;
    }
    inline int Create(){return freelist[freepos++];}
    inline void Delete(int t){return (void)(freelist[--freepos]=t);}
    inline void Find(int& p,int& b){for(b=0;b!=-1&&p>sz[b];b=nxt[b]) p-=sz[b];}
    inline void Fill(int b,int n,char* str,int e){
        if(b==-1) return;
        nxt[b]=e; sz[b]=n;
        memcpy(data[b],str,n);
    }
    inline void Split(int b,int p){
        if(b==-1||p==sz[b]) return;
        int t=Create();
        Fill(t,sz[b]-p,data[b]+p,nxt[b]);
        nxt[b]=t;  sz[b]=p;
    }
    inline void Maintainlist(int b){
        for(;b!=-1;b=nxt[b]){
            for(int t=nxt[b];t!=-1&&sz[b]+sz[t]<=BLOCKSIZE;t=nxt[b]){
                memcpy(data[b]+sz[b],data[t],sz[t]);
                sz[b]+=sz[t]; nxt[b]=nxt[t];  Delete(t);
            }
        }
    }
    inline void Insert(int p,int n,char* str){
        int b,t,i;  Find(p,b); Split(b,p);
        for(i=0;i+BLOCKSIZE<=n;i+=BLOCKSIZE){
            t=Create();
            Fill(t,BLOCKSIZE,str+i,nxt[b]);
            nxt[b]=t; b=t;
        }
        if(n-i){
            t=Create();
            Fill(t,n-i,str+i,nxt[b]);
            nxt[b]=t;
        }
        Maintainlist(b);
    }
    inline void Erase(int p,int n){
        int b,e;  Find(p,b);  Split(b,p);
        for(e=nxt[b];e!=-1&&n>sz[e];e=nxt[e]) n-=sz[e];
        Split(e,n);  e=nxt[e];
        for(int t=nxt[b];t!=e;t=nxt[b]){nxt[b]=nxt[t];Delete(t);}
        Maintainlist(b);
    }
    inline void Get(int p,int n,char*str){
        int b,t,i; Find(p,b); i=min(n,sz[b]-p);  memcpy(str,data[b]+p,i);
        for(t=nxt[b];t!=-1&&i+sz[t]<=n;i+=sz[t],t=nxt[t])memcpy(str+i,data[t],sz[t]);
        if(n-i&&t!=-1) memcpy(str+i,data[t],n-i);  str[n]='\0';
    }
}st;
int main(){
    char order[10];
    int T,pos=0,n;
    read(T);st.Clear();
    while(T--){
        scanf("%s",order);
        switch(order[0]){
            case 'M':read(pos);break;
            case 'I':read(n);char c;
                for (int i=0; i<=n-1; ++i){
                    c=getchar(); str[i]=c;
                    if(c=='\n') --i;
                }
                st.Insert(pos,n,str);
                break;
            case 'D':read(n);st.Erase(pos,n);break;
            case 'G':read(n);st.Get(pos,n,str);puts(str);break;
            case 'P':--pos;break;
            case 'N':++pos;break;
        }
    }
    return 0;
}

点我回到主页

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s