HMF-have much fun Site
文章
标签
16
联系方式戳我~
阅
【题解】CF238D Tape Programming
热度: loading...
杂题清除计划
考虑我们将 的序列整个操作一遍（中途断掉了就跳到下一段，操作前要在最左边加个 防止指针从左边掉出去），然后将指针移动的序列记下来。由于每个数字最多被经过 次，因此序列长度 。
考虑一个询问 , 的操作序列一定是我们之前预处理出的序列的一部分（移动是连续的）。因此考虑直接在序列上使用前缀和求解。
分类讨论：走出 的方式有两种，一种是直接往右走出去，第二种是往右走然后掉头从左边走出去。
处理这两种情况，记下 表示第一次从 往右边走出去时第 个数输出的次数。记下 表示第一次从 右边走到左边 时第 个数输出的次数。注意这里是从 右边走到左边而不是从 走到左边。因为 这个位置可能在一开始往右走的时候就被删掉了，对于删除我们使用链表。
对于如何给被删除的数赋值，我们 表示第 个数右边第一个 没被赋值的数。往左移的时候，对于当前点在链表上的前驱，我们从前驱开始，在下标上移动，给 没被赋值的数赋值后维护 即可。
最后输出时判断有没有从 的左边出来过，分类输出即可。
赏
