题解 P4567 【[AHOI2006]文本编辑器】

· · 题解

日常安利博客

\text{Foreword}

这里不是正解！！！ 这里不是正解！！！

虽说如此，截止到此篇题解发出时间，我的程序仍是最优解第一。并且拉了原先第一还不少

其实原本只是想试试能不能过掉[NOI2003]文本编辑器的，过了之后听同学说这边有个带翻转加强版，于是就来试了试...

然后就A了？然后就最优解第一？？？

满脸问号.jpg

\text{Solution}

题意就不解释了...赤裸裸的数据结构

你可以尝试各类操作，比如 \text{Splay、FHQ}、块状链表\cdots

这些我都不再赘述，前面也有人讲了。

但如果真的到了考场上，这些复杂又难调的数据结构无疑会耗费大量的时间。

再认真的看看数据范围：

暴力，真的就会 \text{TLE} 吗？

如果开启 O_2，\text{vector} 带来的极致速度，还是值得我们一试的。

其实最重要的还是，太好码了！

记当前光标位置为 pos，当前文本为 T，临时文本为 temp。那么各个操作分别为：

$\text{Insert}\ n\ s$：将 $s$ 每个字符依次读入放入 $temp$，然后`T.insert(T.begin() + pos, temp.begin(), temp.end());` $\text{Delete}\ n$：`T.erase(T.begin() + pos, T.begin() + pos + n);` $\text{Rotate}\ n$：`std::reverse(T.begin() + pos, T.begin() + pos + n);` $\text{Get}$：`putchar(T[pos]);` $\text{Prev}$：`--pos;` $\text{Next}$：`++pos;` 有没有直观感受到码量？ 于是花 $\text{20min}$ 时间码完之后，我满怀着希望一交... ...当然是因为细节问题爆零了- -（因用了`assert`，全部 $\text{RE}$） 想详见细节怎么处理的，请看代码（在下面）- - [$\Huge\text{Code}$](https://www.luogu.org/paste/knyyi070) $\text{Thanks for your consideration!}