学过数组和链表的同学肯定知道：
数组支持O(1)访问，而插入则需要O(N)；
链表支持O(1)插入，二访问却需要O(N)。
那么问题来了：
如果有道题，需要你动态插入并随时访问，同时还卡你空间，怎么办？
例题：[NOI2003]Editor
题目要求你的算法/数据结构资瓷插入区间,删除区间,访问区间，空间也卡到了162MB。
于是。怎么写？
说rope的出门右转,rope是C++11的,CCF系列赛事一般不支持哟
而且比块状链表慢！
准备瞎扯：
块状链表是数组与链表的结合体，链表上的每个点都是一个数组集合
非常nice地资瓷的查询和插入以及删除。空间小，速度快，值得你拥有。
首先，第一个操作-定位：
你总需要知道你要找的东西在哪一个块里吧。
大概类似Splay找第k大？
假设你要找下标p所在的块，因为你知道每个块的大小，你就从头扫到尾，每扫一个块都减去那个块的大小。
直到减为负数。(不是很会表达，大概懂意思就好辣！！)
第二个操作-维护块状链表形态：
为了保证效率，块状链表的形态是需要维护的，不维护形态的话可以随便卡成链表(就是每个块的大小为1)。
做法大概就是：
你从头扫到尾，若发现某个块比较小，比如大小小于的块，你就可以把它和后面那个块合并，合并的条件有很多种版本，一般都是在区间
内的。
合并的话也不难：
直接把一个块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;
}
