自动搬运

查看原文

来自洛谷，原作者为

	EndSaH 我将凋零，凋零在这片我爱的土地。

搬运于2025-08-24 22:01:26，当前版本为作者最后更新于2019-02-12 12:38:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

日常安利博客

$\text{Foreword}$

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

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

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

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

满脸问号.jpg

$\text{Solution}$

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

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

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

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

再认真的看看数据范围：

$\text{MOVE}$ 操作不超过 $50000$ 个，$\text{INSERT, DELETE, ROTATE}$ 操作的总个数不超过 $6000$，$\text{GET}$ 操作不超过 $20000$ 个， $\text{PREV, NEXT}$ 操作的总个数不超过 $20000$。

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

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

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

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

$\text{Move}\ k$：pos = k;

$\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}$

$\text{Thanks for your consideration!}$