问题描述:
文本：由 0 个或多个 ASCII 码在区间[32，126] 内的字符构成的序列
光标：在一段文本中用于指示位置的标记，可以位于文本首部、文本尾部或文本的某两个字符之间。
文本编辑器：由一段文本和该文本中的一个光标组成，支持如下操作：
MOVE k：将光标移动到第 k 个字符之后，如果 k = 0，将光标移动到文本开头；
INSERT n s：在光标处插入长度为n的字符串 s，光标位置不变,n ≥ 1；
DELETE n：删除光标后的n个字符，光标位置不变,n ≥ 1；
GETn n：输出光标后的n 字符,光标位置不变，n ≥ 1；
PREV：光标前移一个字符；
NEXT：光标后移一个字符；
数据范围：MOVE操作总个数不超过 50000，INSERT 和 DELETE 操作总个数不超过4000，PREV 和 NEXT 操作总个数不超过 200000。所有 INSERT 插入的字符数之和不超过2MB，正确的输出文件长度不超过 3MB。
| 输入样例 | 输出样例 |
| 15 Insert 26 abcdefghijklmnop qrstuv wxy Move 15 Delete 11 Move 5 Insert 1 ^ Next Insert 1 _ Next Next Insert 4 .\/. Get 4 Prev Insert 1 ^ Move 0 Get 22 | .\/. abcde^_^f.\/.ghijklmno |
分块 + 链表
#include<bits/stdc++.h>
using namespace std;
int block = 2500; //一个块的标准大小 = sqrt(n)，n约等于6M
list<vector<char> > List; //整体是链表，链表的每个元素是一个块
typedef list<vector<char> >::iterator it; //自定义数据类型名称
it Find(int &pos) { //返回块，并更新x为这个块中的位置
for (it i = List.begin(); ;i++) { //逐个找链表上的每个块
if(i == List.end() || pos <= i->size()) return i; //等于最后一个元素或者在这个块的范围里
pos -= i->size(); //下一个块：每经过一个块，就更新x
}
}
void Output(int L, int R) { // [L, R)
it L_block = Find(L), R_block = Find(R);
for (it it1 = L_block; ; it1++){ //打印每个块
int a; it1 == L_block ? a=L : a=0; //一个块的起点
int b; it1 == R_block ? b=R : b=it1->size(); //块的终点
for (int i = a; i < b; i++) putchar(it1->at(i));
if(it1 == R_block) break; //迭代器it不能用 <= ，只有 == 和 !=
}
putchar('\n');
}
it Next(it x){return ++x; } //返回下一个块
void Merge(it x) { //合并块x和块x+1
x->insert(x->end(), Next(x)->begin(), Next(x)->end()); //合并
List.erase(Next(x)); //删掉多余元素快
}
void Split(it x, int pos){ //把第x个块在这个块的pos处分成2块
if (pos == x->size()) return; //pos在这个块的末尾
List.insert(Next(x), vector<char>(x->begin() + pos, x->end())); //把pos后面的部分划给下一个块
x->erase(x->begin() + pos, x->end()); //删除划出的部分
}
void Update(){ //把每个块重新划成等长的块
for (it i = List.begin(); i != List.end(); i++){
while (i->size() >= (block << 1)) //如果块大于2个block，分开
Split(i, i->size() - block);
while (Next(i) != List.end() && i->size() + Next(i)->size() <= block) //如果块+下一个块小于block，合并
Merge(i);
while (Next(i) != List.end() && Next(i)->empty()) //删除最后的空块
List.erase(Next(i));
}
}
void Insert(int pos, const vector<char>& ch){ //在pos处插入ch
it curr = Find(pos);
if (!List.empty()) Split(curr, pos); //把一个块拆为两个
List.insert(Next(curr), ch); //把字符串插到两个块中间
Update();
}
void Delete(int L, int R) { // [L, R)删除区间（L,R）
it L_block, R_block;
L_block = Find(L); Split(L_block, L); //删除区间的左边块位置
R_block = Find(R); Split(R_block, R); //删除区间的右边块位置
R_block++;
while(Next(L_block) != R_block) List.erase(Next(L_block)); //删掉删除区间里的所有块
Update();
}
int main(){
vector<char> ch; int len, pos, n;
cin >> n; //例子个数
while (n--) {
char opt[7]; cin >> opt; //六个操作之一
if(opt[0]=='M') cin >> pos; //写入光标变量
if(opt[0]=='I'){
ch.clear(); cin >> len; ch.resize(len); //调整向量容器的大小
for (int i = 0; i < len; i++){
ch[i] = getchar();
while(ch[i]<32||ch[i]>126) ch[i]=getchar(); //读一个合法字符
}
Insert(pos, ch); //把字符串插入到链表中
}
if(opt[0]=='D'){ cin >> len; Delete(pos, pos + len); }
if(opt[0]=='G'){ cin >> len; Output(pos, pos + len); }
if(opt[0]=='P') pos--; //光标变量自减
if(opt[0]=='N') pos++; //光标变量自增
}
return 0;
}
笔记：用pos变量储存现在的光标位置，区间删除是先找到删除区间的左右节点，将分块里的左区间节点往后的再单独建立一个分块，右区间往前也是，删除掉的就只有整块，再用Update()函数重新分块储存。插入是先找到块和插入的节点，将插入的当前块分成两部分，在两个块中间插入新的元素块储存新元素，最后也用Update()函数重新分块储存。
FHQ Treap应用
#include<bits/stdc++.h>
using namespace std;
const int M = 2e6+10;
int root = 0,cnt = 0;
struct Node{int ls,rs; char val; int pri; int size;}t[M]; //tree[]存树
void Update(int u){t[u].size = t[t[u].ls].size + t[t[u].rs].size+1;} //用于排名分裂
int newNode(char x){ //建立只有一个点的树
cnt++;
t[cnt].size = 1; t[cnt].pri = rand(); t[cnt].ls = t[cnt].rs = 0;
t[cnt].val = x; //一个字符
return cnt;
}
void Split(int u,int x,int &L,int &R){ //排名分裂，不是权值分裂
if(u == 0){L = R = 0; return ;}
if(t[t[u].ls].size+1 <= x){ //第x个数在u的右子树上
L = u; Split(t[u].rs, x-t[t[u].ls].size-1, t[u].rs, R);
}
else{R = u; Split(t[u].ls,x,L,t[u].ls); } //第x个数在左子树上
Update(u);
}
int Merge(int L,int R){ //合并
if(L==0 || R==0) return L+R;
if(t[L].pri > t[R].pri){ t[L].rs = Merge(t[L].rs,R); Update(L); return L; }
else{ t[R].ls = Merge(L,t[R].ls); Update(R); return R;}
}
void inorder(int u){ //中序遍历，打印结果
if(u == 0) return;
inorder(t[u].ls); cout << t[u].val; inorder(t[u].rs);
}
int main(){
srand(time(NULL));
int len, L, p, R, pos = 0; //p是第三棵树，pos是光标的当前位置
int n; cin>>n; //操作次数
while(n--){
char opt[10]; cin>>opt; //操作名称
if(opt[0]=='M') cin>>pos; //移动光标
if(opt[0]=='I'){ //插入len个字符
cin>>len;
Split(root,pos,L,R);
for(int i=1;i<=len;i++) { //逐个读入字符
char ch=getchar(); while(ch<32||ch>126) ch=getchar();
L = Merge(L,newNode(ch)); //把字符加到树中
}
root = Merge(L,R); //根节点更新
}
if(opt[0]=='D'){ //删除光标后len个字符
cin>>len; Split(root,pos+len,L,R); Split(L,pos,L,p); //分裂成三棵树，中间删除的len去掉不合并
root = Merge(L,R);
}
if(opt[0]=='G'){ //打印len个字符
cin>>len; Split(root,pos+len,L,R); Split(L,pos,L,p); //分裂成三棵树，中间树中序遍历
inorder(p); cout<<"\n"; //打印
root = Merge(Merge(L,p),R);
}
if(opt[0]=='P') pos--;
if(opt[0]=='N') pos++;
}
return 0;
}
笔记：删除操作和打印操作比较有意思，一共分裂了两次，先分裂成两棵树，将其中一颗树再分裂成两棵树。分裂是按照排名分裂不是权值分裂。
Splay的常用操作和代码
#include<bits/stdc++.h>
using namespace std;
const int M = 2e6+10;
int cnt, root;
struct Node{int fa,ls,rs,size; char val;}t[M]; //tree[]存树;
void Update(int u){t[u].size = t[t[u].ls].size + t[t[u].rs].size+1;} //用于排名
char str[M]={0}; //一次输入的字符串
int build(int L,int R,int f){ //把字符串str[]建成平衡树
if(L>R) return 0; //到头返回
int mid = (L+R)>>1; //寻找区间中点
int cur = ++cnt; //加入的字符
t[cur].fa = f; //写入父节点
t[cur].val= str[mid]; //中序方式放入字符串
t[cur].ls = build(L,mid-1,cur); //左递归放入字符串
t[cur].rs = build(mid+1,R,cur); //右递归放入字符串
Update(cur); //向上更新
return cur; //返回新树的根
}
int get(int x){return t[t[x].fa].rs == x;} //如果u是右儿子，返回1；左儿子返回0
void rotate(int x){ //单旋一次
int f=t[x].fa, g=t[f].fa, son=get(x); //f:父亲；g：祖父
if(son==1) { //x是右儿子，左旋zag
t[f].rs = t[x].ls; //子节点的左儿子赋值给父节点的右儿子
if(t[f].rs) t[t[f].rs].fa = f; //更换父节点，分裂出x节点与x的右子节点
}
else { //x是左儿子，右旋zig
t[f].ls = t[x].rs;
if(t[f].ls) t[t[f].ls].fa = f;
}
t[f].fa=x; //x旋为f的父结点
if(son == 1) t[x].ls=f; //左旋，f变为x的左儿子
else t[x].rs=f; //右旋，f变为x的右儿子
t[x].fa = g; //x现在是祖父的儿子
if(g){ //更新祖父的儿子
if(t[g].rs==f) t[g].rs = x;
else t[g].ls = x;
}
Update(f); Update(x);
}
void splay(int x,int goal){ //goal=0,新的根是x；goal!=0,把x旋为goal的儿子
if(goal == 0) root=x;
while(true){
int f = t[x].fa, g=t[f].fa; //一次处理x（子节点）,f（父节点）,g（祖父节点）三个点
if(f == goal) break; //x的父节点旋到goal跳出循环
if(g != goal) { //有祖父，分一字旋和之字旋两种情况
if(get(x)==get(f)) rotate(f); //xfg三节点在一条直线上：一字旋，先旋f、g
else rotate(x);} //xfg三节点不在一条直线上：之字旋，直接旋x
rotate(x);
}
Update(x);
}
int kth(int k,int u){ //第k大数的位置
if( k == t[t[u].ls].size + 1) return u; //返回位置
if( k <= t[t[u].ls].size ) return kth(k,t[u].ls); //在左子树
if( k >= t[t[u].ls].size + 1) return kth(k-t[t[u].ls].size-1,t[u].rs); //在右子树
}
void Insert(int L,int len){ //插入一段区间
int x = kth(L,root), y = kth(L+1,root); //x:第L个数的位置，y:第L+1个数的位置
splay(x,0); splay(y,x); //分裂
//先把x旋到根，然后把y旋到x的儿子，此时y是x的右儿子，且y的左儿子为空
t[y].ls = build(1,len,y); //合并：建一棵树，挂到y的左儿子上
Update(y); Update(x); //更新最后两个节点：y子节点，x父节点
}
void del(int L,int R){ //删除区间[L+1,R]
int x=kth(L,root), y=kth(R+1,root);
splay(x,0); splay(y,x); //y是x的右儿子，y的左儿子是待删除的区间
t[y].ls=0; //剪断左子树，等于直接删除。这里为了简单，没有释放空间
Update(y); Update(x);
}
void inorder(int u){ //中序遍历
if(u==0) return;
inorder(t[u].ls);cout<<t[u].val;inorder(t[u].rs);
}
int main(){
t[1].size=2; t[1].ls=2; //小技巧：虚拟祖父，防止旋转时越界而出错
t[2].size=1; t[2].fa=1; //小技巧：虚拟父亲
root=1; cnt=2; //在操作过程中，root将指向字符串的根
int pos=1; //光标位置
int n; cin>>n;
while(n--){
int len; char opt[10]; cin>>opt;
if(opt[0]=='I'){
cin>>len;
for(int i=1;i<=len;i++){
char ch=getchar(); while(ch<32||ch>126) ch=getchar();
str[i] = ch;
}
Insert(pos,len);
}
if(opt[0]=='D'){ cin>>len; del(pos,pos+len);} //删除区间[pos+1,pos+len]
if(opt[0]=='G'){
cin>>len; int x=kth(pos,root), y=kth(pos+len+1,root);
splay(x,0); splay(y,x);
inorder(t[y].ls); cout<<"\n";
}
if(opt[0]=='M'){ cin>>len; pos=len+1;}
if(opt[0]=='P') pos--;
if(opt[0]=='N') pos++;
}
}
笔记：splay树是通过旋转将节点转到二叉树的根部，rotate()函数是单旋一次，左旋是zag，右旋是zig，splay()函数分两种旋转情况，一个是一字旋，节点都是做儿子或者右儿子，另外一种是之字旋，节点左右儿子都有。插入操作是将树以pos分成L和R两棵树，L树的最右节点x旋转为根节点，R树的最左节点y为根节点的右子树，将插入的数据放在y节点的左子树上。删除同插入，但是y的左子树是删除的区间。