题目描述
你需要写一个文本编辑器，支持：
-
Move k：将光标移动到第走个字符之后，如果 \(k=0\)，将光标移到文本第一个字符之前。 -
Insert n (换行) S：在光标后插入长度为 \(n\) 的字符串 \(S\)，光标位置不变，\(n \ge 1\)。 -
Delete n：删除光标后的 \(n\) 个字符，光标位置不变，\(n \ge 1\)。 -
Rotate n：反转光标后的 \(n\) 个字符，光标位置不变，\(n \ge 1\)。 -
Get：输出光标后的一个字符，光标位置不变。 -
Prev：光标前移一个字符。 -
Next：光标后移一个字符。
操作次数 \(m\) 满足 \(1 \leq m \leq 10^5\) ，插入的总字符不超过 \(2^{21}\) 个。
Solution
和 [NOI2003] 文本编辑器 基本一样，不过多了个 Rotate ，并且是输出单个字符的。
其他的操作我在 题解 P4008 [NOI2003] 文本编辑器 已经写过了，这里就不写了。
对于 Rotate 操作，我们只需要把排名为 \(pos+1\) 的节点 \(ls\) 旋转到根，把排名为 \(pos+len+2\) 的节点 \(rs\) 旋转到 \(l\) 下面。
然后给 \(rs\) 的左儿子打上一个翻转标记，同时交换左右儿子。
然后每次在查找排名为 \(k\) 的节点的时候记得 \(pushdown\) 。
就……没了？
但是这个题目有几个坑：
- 虽然题目说了字符的 ASCII 码在 \([32,126]\) 之间，但是其实换行也算是一个字符，所以读入的时候不要把换行忽略。
（我在做题的时候："editor有7个字母？"） - 如果当前输出的字符是换行，那么不要再输出一个换行了 。
代码如下：
#include <cstdio>
#include <cstring>
#include <cctype>
inline int read() {
int num = 0 ,f = 1; char c = getchar();
while (!isdigit(c)) f = c == '-' ? -1 : f ,c = getchar();
while (isdigit(c)) num = (num << 1) + (num << 3) + (c ^ 48) ,c = getchar();
return num * f;
}
inline int min(int a ,int b) {return a < b ? a : b;}
inline int max(int a ,int b) {return a > b ? a : b;}
inline void swap(int &a ,int &b) {int t = a; a = b; b = t;}
const int N = 1 << 22;
struct Splay {
struct node {
int ch[2] ,fa ,size ,rev;
char val;
node () : fa(0) ,size(0) ,rev(0) ,val(0) {}
}t[N]; int root ,tot;
Splay() : root(0) ,tot(0) {}
inline void update(int now) {
t[now].size = t[t[now].ch[0]].size + t[t[now].ch[1]].size + 1;
}
inline void puttag(int now) {
swap(t[now].ch[0] ,t[now].ch[1]);
t[now].rev ^= 1;
}
inline void pushdown(int now) {
if (t[now].rev == 0) return ;
puttag(t[now].ch[0]);
puttag(t[now].ch[1]);
t[now].rev ^= 1;
}
inline void rotate(int x) {
int y = t[x].fa ,z = t[y].fa ,k = t[y].ch[1] == x;
t[x].fa = z; t[z].ch[t[z].ch[1] == y] = x;
t[y].ch[k] = t[x].ch[k ^ 1]; t[t[x].ch[k ^ 1]].fa = y;
t[x].ch[k ^ 1] = y; t[y].fa = x;
update(y); update(x);
}
inline void splay(int x ,int goal) {
while (t[x].fa != goal) {
int y = t[x].fa ,z = t[y].fa;
if (z != goal) {
if ((t[z].ch[1] == y) == (t[y].ch[1] == x)) rotate(y);
else rotate(x);
}
rotate(x);
}
if (goal == 0) root = x;
}
inline int findval(int rank) {
int now = root;
while (now) {
pushdown(now); //记得 pushdown
int l = t[now].ch[0];
if (t[l].size >= rank) now = l;
else if (t[l].size + 1 >= rank) return now;
else rank -= t[l].size + 1 ,now = t[now].ch[1];
}
return 0;
}
inline void build(int &now ,int fa ,int l ,int r ,char *s) {
if (l > r) return ;
int mid = (l + r) >> 1;
now = ++tot;
t[now].val = s[mid];
t[now].fa = fa;
build(t[now].ch[0] ,now ,l ,mid - 1 ,s);
build(t[now].ch[1] ,now ,mid + 1 ,r ,s);
update(now);
}
inline void insert(int st ,int len ,char *s) {
int l = findval(st + 1) ,r = findval(st + 2);
splay(l ,0); splay(r ,l);
build(t[r].ch[0] ,r ,1 ,len ,s); update(r); update(l);
}
inline void remove(int st ,int ed) {
int l = findval(st) ,r = findval(ed + 2);
splay(l ,0); splay(r ,l);
int now = t[r].ch[0];
t[now].fa = t[r].ch[0] = 0; update(r); update(l);
}
inline void reverse(int st ,int ed) {
int l = findval(st) ,r = findval(ed + 2);
splay(l ,0); splay(r ,l);
int now = t[r].ch[0];
puttag(now); update(r); update(l);
}
inline void get(int pos) {
int l = findval(pos + 1) ,r = findval(pos + 3);
splay(l ,0); splay(r ,l);
int now = t[r].ch[0];
if (t[now].val != '\n') putchar(t[now].val); //记得特判
puts("");
}
}t;
int pos ,n; char opt[10] ,s[N];
signed main() {
n = read();
t.build(t.root ,0 ,1 ,2 ,s);
while (n--) {
scanf("%s" ,opt);
if (opt[0] == 'M') pos = read();
else if (opt[0] == 'I') {
int len;
scanf("%d" ,&len); getchar();
//s[1] = ' ';
for (int i = 1; i <= len; i++) s[i] = getchar();
t.insert(pos ,len ,s);
}
else if (opt[0] == 'D') {
int len = read(); t.remove(pos + 1 ,pos + len);
}
else if (opt[0] == 'R') {
int len = read(); t.reverse(pos + 1 ,pos + len);
}
else if (opt[0] == 'G') t.get(pos);
else if (opt[0] == 'P') pos--;
else if (opt[0] == 'N') pos++;
}
return 0;
}