$ color{#0066ff}{ 题目描述 }$
很久很久以前，(DOS3.x) 的程序员们开始对 (EDLIN) 感到厌倦。于是，人们开始纷纷改用自己写的文本编辑器⋯⋯
多年之后，出于偶然的机会，小明找到了当时的一个编辑软件。进行了一些简单的测试后，小明惊奇地发现：那个软件每秒能够进行上万次编辑操作（当然，你不能手工进行这样的测试） ！于是，小明废寝忘食地想做一个同样的东西出来。你能帮助他吗？
为了明确目标，小明对“文本编辑器”做了一个抽象的定义:
文本：由 (0) 个或多个 ASCII 码在闭区间[(32), (126)]内的字符构成的序列。
光标：在一段文本中用于指示位置的标记，可以位于文本首部，文本尾部或文本的某两个字符之间。
文本编辑器：由一段文本和该文本中的一个光标组成的，支持如下操作的数据结构。如果这段文本为空，我们就说这个文本编辑器是空的。
| 操作名称 | 输入文件中的格式 | 功能 |
|---|---|---|
| (MOVE(k)) | Move k | 将光标移动到第 k个字符之后，如果 k=0，将光标移到文本开头 |
| (INSERT(n,s)) | Insert n s | 在光标处插入长度为n的字符串s，光标位置不变n≥1 |
| (DELETE(n)) | Delete n | 删除光标后的n个字符，光标位置不变，n ≥ 1 |
| (GET(n)) | Get n | 输出光标后的n个字符，光标位置不变，n ≥ 1 |
| (PREV()) | Prev | 光标前移一个字符 |
| (NEXT()) | Next | 光标后移一个字符 |
你的任务是：
- 建立一个空的文本编辑器。
- 从输入文件中读入一些操作并执行。
- 对所有执行过的 GET 操作，将指定的内容写入输出文件。
(color{#0066ff}{输入格式})
输入文件 editor.in 的第一行是指令条数 t，以下是需要执行的 t 个操作。其中：
为了使输入文件便于阅读， Insert 操作的字符串中可能会插入一些回车符， 请忽略掉它们（如果难以理解这句话，可以参照样例） 。
除了回车符之外，输入文件的所有字符的 ASCII 码都在闭区间[32, 126]内。且
行尾没有空格。
这里我们有如下假定：
- MOVE 操作不超过 50000 个， INSERT 和 DELETE 操作的总个数不超过 4000，
PREV 和 NEXT 操作的总个数不超过 200000。
- 所有 INSERT 插入的字符数之和不超过 2M（1M=1024*1024 字节） ，正确的输出文件长度不超过 3M 字节。
- DELETE 操作和 GET 操作执行时光标后必然有足够的字符。 MOVE 、 PREV 、 NEXT
操作必然不会试图把光标移动到非法位置。
- 输入文件没有错误。
对 对 C++ 选手的提示：经测试，最大的测试数据使用 fstream 进行输入有可能会比使用进行输入有可能会比使用 stdio 慢约 1 秒。*
(color{#0066ff}{输出格式})
输出文件 editor.out 的每行依次对应输入文件中每条 Get 指令的输出。
(color{#0066ff}{输入样例})
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
(color{#0066ff}{输出样例})
./.
abcde^_^f./.ghijklmno
(color{#0066ff}{数据范围与提示})
对于20%的数据，满足1 ≤ N, M ≤ 20。
另有20%的数据，满足所有“#”都属于某一个正确的细胞。
对于100%的数据，满足1 ≤ N, M ≤ 1,000。
(color{#0066ff}{题解})
Splay维护这个文本
注意光标的位置以及边界的细节
#include<bits/stdc++.h>
#define LL long long
LL in() {
char ch; LL x = 0, f = 1;
while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
return x * f;
}
const int maxn = 2e6 + 10;
struct Splay {
protected:
struct node {
node *ch[2], *fa;
int siz;
char val;
node(node *fa = NULL, int siz = 1, char val = 3): fa(fa), siz(siz), val(val) {
ch[0] = ch[1] = NULL;
}
bool isr() { return this == fa->ch[1]; }
void upd() {
siz = 1;
if(ch[0]) siz += ch[0]->siz;
if(ch[1]) siz += ch[1]->siz;
}
int rk() { return ch[0]? ch[0]->siz + 1 : 1; }
}pool[maxn], *tail, *root;
std::queue<node *> q;
void rot(node *x) {
node *y = x->fa, *z = y->fa;
bool k = x->isr(); node *w = x->ch[!k];
if(y != root) z->ch[y->isr()] = x;
else root = x;
(x->ch[!k] = y)->ch[k] = w;
(y->fa = x)->fa = z;
if(w) w->fa = y;
y->upd(), x->upd();
}
void splay(node *o, node *p) {
while(o->fa != p) {
if(o->fa->fa != p) rot(o->isr() ^ o->fa->isr()? o : o->fa);
rot(o);
}
}
node *kth(int k) {
node *o = root;
while(o->rk() != k) {
if(o->rk() < k) k -= o->rk(), o = o->ch[1];
else o = o->ch[0];
}
return o;
}
void split(int l, int r) { splay(kth(l), NULL), splay(kth(r + 2), root); }
node *build(node *fa, int l, int r, char *a) {
if(l > r) return NULL;
node *o;
if(!q.empty()) o = q.front(), q.pop();
else o = new(tail++) node();
int mid = (l + r) >> 1;
*o = node(fa, 1, a[mid]);
o->ch[0] = build(o, l, mid - 1, a);
o->ch[1] = build(o, mid + 1, r, a);
return o->upd(), o;
}
void dfs(node *o) {
if(o->ch[0]) dfs(o->ch[0]);
if(o->ch[1]) dfs(o->ch[1]);
q.push(o);
}
void out(node *o) {
if(o->ch[0]) out(o->ch[0]);
putchar(o->val);
if(o->ch[1]) out(o->ch[1]);
}
public:
Splay() {
root = NULL;
while(!q.empty()) q.pop();
tail = pool;
}
void ins(int l, int r, int len, char *s) {
node *o = build(NULL, 1, len, s);
split(l, r);
(root->ch[1]->ch[0] = o)->fa = root->ch[1];
root->ch[1]->upd(), root->upd();
}
void del(int l, int r) {
split(l, r);
dfs(root->ch[1]->ch[0]);
root->ch[1]->ch[0] = NULL;
root->ch[1]->upd(), root->upd();
}
void getans(int l, int r) {
split(l, r);
out(root->ch[1]->ch[0]);
}
void build(int len, char *s) { root = build(NULL, 1, len, s); }
}s;
char getch() {
char ch = getchar();
while(ch < 32 || ch > 126) ch = getchar();
return ch;
}
int len;
char t[maxn], ls[22], b[3];
int main() {
b[1] = b[2] = '$';
s.build(2, b);
int now = 0, x;
for(int T = in(); T --> 0;) {
scanf("%s", ls);
if(ls[0] == 'M') now = in();
if(ls[0] == 'I') {
x = in();
for(int i = 1; i <= x; i++) t[i] = getch();
s.ins(now + 1, now, x, t);
}
if(ls[0] == 'D') s.del(now + 1, now + in());
if(ls[0] == 'G') s.getans(now + 1, now + in()), putchar('
');
if(ls[0] == 'P') now--;
if(ls[0] == 'N') now++;
}
return 0;
}