传送门
看了看块状链表，就是数组和链表的合体。
看上去好高大尚，思想也很简单。
但是发现代码量也不是很小，而且代码理解起来也是费尽得很，倒不如splay用起来顺手。
在加上适用范围貌似不是特别广，所以只把模板贴在这，只当了解思想，暂时先不使用。（也不会用啊）
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<queue> 5 using namespace std; 6 7 const int N=1<<25; 8 const int blocksize=20000; 9 const int blocknum=N/blocksize*3; 10 11 int T,_; 12 int cur; 13 char str[5000005],opt[100]; 14 queue <int> q; 15 struct node 16 a[blocknum+1000]; 20 21 void init() 22 26 void read(int len) 27 36 } 37 //新开一个块的节点 38 int newnode() 39 43 //回收块的节点 44 void delnode(int t) 45 48 //找到pos所在的块，并使pos表示在当前块中的位置 49 void find(int &pos,int &now) 50 54 //将新快赋值 55 void fillnode(int pos,int n,char data[],int nxt) 56 60 //将块pos在p位置前后分开，变成两个块 61 void split(int pos,int p) 62 68 //把碎块合并 69 void maintain(int pos) 70 78 } 79 //在光标pos处插入长度为n的str 80 void insert(int pos,int n) 81 93 if (i<n) 94 99 maintain(now); 100 } 101 //从光标pos开始删除长度为n的字符串 102 void del(int pos,int n) 103 116 //从pos这个位置开始输出长度为n的字符串 117 void get(int pos,int n) 118 128 if (i<n&&t!=1) memcpy(str+i,a[t].data,ni); 129 str[n]=0; 130 } 131 int main() 132 145 if (opt[0]=='P') cur;//光标左移 146 if (opt[0]=='N') cur++;//光标右移 147 if (opt[0]=='D')//删除一段区间 148 152 if (opt[0]=='G')//输出一段区间 153 158 } 159 }View Code
上一篇：【模板】prim的heap优化
下一篇：[HDU2222]Keywords Search（AC自动机）
模板 块状链表
