NOI2003 文本编辑器 题解

\STL大法好/

正规解法块状链表，这里采取的是黑科技解法。

rope是扩展STL库中的一个数据结构——可持久化平衡树,相比较set，它更适合区间插入和删除。这里用来解此题，就显得十分傻瓜容易了。

头文件：#include <ext/rope>

命名空间：using namespace __gnu_cxx;

基本操作：

insert(pos, s)将字符串s插入pos位置

erase(pos, num)从pos开始删除num个字符

copy(pos, len, s)从pos开始len个字符用s代替

substr(pos, len)提取pos开始的len个字符

at(x)访问第x个元素

几乎跟题目一模一样！

更开心的是，rope在NOI中是允许使用的（hooray）！

于是代码就十分简单了：

#include <bits/stdc++.h>
#include <ext/rope>

using namespace __gnu_cxx;
using namespace std;

rope <char> editor;

char ch;
string oper;
int pos, n, rela;

int main()
{
	cin.tie(0);
	cout.tie(0);
	
	scanf("%d", &n);
	
	while(n--)
	{
	    cin >> oper;
	    scanf("%d", &rela);
	    
		if(oper =="Insert"){
		    int pos1 = pos;
			while(rela)
			{
				ch = getchar();
				if((int)ch >= 32 && (int)ch <= 126){
				    editor.insert(pos1, ch);
				    rela--;
				    pos1++;
				}
			}
        }
        
        else if(oper =="Move"){
        	pos = rela;
        }
        
        else if(oper =="Next"){
            pos++;
        }
        
        else if(oper =="Prev"){
        	pos--;
        }
        
        else if(oper =="Get"){
        	cout << editor.substr(pos, rela) << endl;
        }
        
        else if(oper =="Delete"){
        	editor.erase(pos, rela);
        }
	}
	return 0;
}

双倍经验 P4567 【AHOI2006】 文本编辑器

此题是上题的升级版，因为要实现rotate操作，所以存储两个rope，一正一反。

代码基本相同，略。