块状链表（尚未完善）
对于线性表，可以 \(O(1)\) 的访问，但是插入和删除操作是 \(O(n)\)
对于链表，可以 \(O(1)\) 的进行插入和删除，但是是 \(O(n)\) 的访问。
于是本着分块的思想，有了块状链表 。
大概长这个样子。每个块的大小数量级在 \(O(\sqrt{n})\) , 块数的量级 \(O(\sqrt{n})\)
主要有以下几种操作：
插入
1.分裂节点 \(O(\sqrt{n})\)
2.在分裂点插入 \(O(\sqrt{n})\)
删除
1.删除开头节点的后半部分 \((\sqrt{n})\)
2.删除中心完整节点 \(O(\sqrt{n})\)
3.删除结尾节点的前半部分 \(O(\sqrt{n})\)
合并
为了保证正确的复杂度，要不定期的进行合并操作。
所谓合并操作，就是从第一个块开始，如果把下一个块合并过来之后大小不大于 \(O(\sqrt{n})\)，就把两个块合并
若没有合并操作，则可能会有很多小块，导致 TLE
P4008 [NOI2003] 文本编辑器
暂时不想打，有时间的话会补回来的
可持久化杀手——rope
#include<ext/rope> // 头文件
using namespace __gnu_cxx; //引用 rope
rope<char> a; //建立一个存储 char 的 rope
// rope<变量类型> 变量名称;
crope a; //实际就是 rope<char> a
// 下标从 0 开始
a.push_back(x) //在末尾添加 x
a.insert(pos, x) //在 pos 插入 x
a.erase(pos, x) //从 pos 开始删除 x个
a.replace(pos, x) //从 pos 开始换成 x
a.substr(pos, x) //提取 pos开始 x个
a.at(x) / a[x] //访问第 x个元素
a.length() / a.size() //返回 a 的大小
a.copy(pos, x, s) //将从 pos位置开始 x个元素提取到 s中 O(1)
a.append(string &s / int *a, int 串s的起始位置, int 长度) //插入 s的 pos开始的 n位 （暂时还不知道怎么用）
//如果需要翻转平衡树，就维护一正一反两个rope，翻转就把两个rope交换一下就行了。
P4008 [NOI2003] 文本编辑器
用上述的操作就可以实现了
#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
return x * f;
}
crope a;
int m, pos;
inline void in(int x){
int pos1 = pos;
while(x){
char ch = getchar();
if((int)ch >= 32 && (int)ch <= 126) a.insert(pos1, ch), --x, pos1++;
}
return ;
}
int main(){
m = read();
while(m--){
char opt[51]; scanf("%s", opt + 1);
if(opt[1] == 'M') pos = read();
else if(opt[1] == 'I') in(read());
else if(opt[1] == 'D') a.erase(pos, read());
else if(opt[1] == 'G') cout << a.substr(pos, read()) << endl;
else if(opt[1] == 'P') --pos;
else if(opt[1] == 'N') ++pos;
}
return 0;
}
P4567 [AHOI2006]文本编辑器
较上题多了反转操作，我们可以维护两个 rope ，一个正序，一个逆序
#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
const int N = 1 << 22;
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
return x * f;
}
rope<char> a, b, t;
int m, pos;
char a1[N], a2[N];
inline void in(int x){
int pos1 = pos;
for(int i = 0; i < x; ++i) a1[i] = a2[x - i - 1] = getchar();
a1[x] = '\0', a2[x] = '\0';
int len = a.size();
a.insert(pos, a1), b.insert(len - pos, a2);
return ;
}
inline void del(int x){
int len = a.size();
a.erase(pos, x), b.erase(len - pos - x, x);
}
inline void rotate(int x){
int len = a.size();
t = a.substr(pos, x);
a = a.substr(0, pos) + b.substr(len - pos - x, x) + a.substr(pos + x, len - pos - x);
b = b.substr(0, len - pos - x) + t + b.substr(len - pos, pos);
}
inline void out(){
putchar(a[pos]);
if(a[pos] != '\n') putchar('\n');
}
int main(){
cin.tie(0), cout.tie(0);
m = read();
while(m--){
char opt[51]; scanf("%s", opt + 1);
if(opt[1] == 'M') pos = read();
else if(opt[1] == 'I') in(read());
else if(opt[1] == 'D') del(read());
else if(opt[1] == 'G') out();
else if(opt[1] == 'P') --pos;
else if(opt[1] == 'N') ++pos;
else if(opt[1] == 'R') rotate(read());
}
return 0;
}
P3850 [TJOI2007]书架
按题意操作即可
#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
const int N = 2e5 + 51;
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
return x * f;
}
int n, m, q;
rope<int> a;
string s[N];
int main(){
cin.tie(0), cout.tie(0);
n = read();
for(int i = 1; i <= n; ++i) cin >> s[i], a.push_back(i);
m = read();
for(int i = 1; i <= m; ++i) cin >> s[i + m], a.insert(read(), i + m);
q = read();
while(q--) cout << s[a.at(read())] << endl;
return 0;
}