ARC072C Alice in linear land

题意 ： 维护一个变量 ，初始值为 。

给出长度为 的指令序列 。

依次执行 ，对于 ，令 。

给出 次询问，每次给出 ，允许对 进行任意修改，判定能否使得 执行完成后 不为 。

询问之间独立。

，时限 。

---

对于某个操作，可以将操作序列分为 前缀 / 被操作的一个元素 / 后缀 三个部分。

记操作 执行完后 的值为 ，容易预处理。

对于修改 的操作，先取出 ，然后通过 ，能（且只能）得到 中的数。

现在问题转化为：对于每个后缀，求出是否存在 中的初始值，使得操作结果不为 。

---

记 表示初始值为 时，执行 会不会得到 。

能列出如下转移：

整个 的复杂度是 ，无法通过。

注意到 的决策是固定的（转移 是一个内向树），没有“最优化”成分。

这些状态之间的贡献关系并不紧密，尝试对状态进行简化。

我们在询问中需要判定 中是否存在 。可以只关心 中最靠前的一个 。

记 为通过 不会变为 的最小的数。

有转移：

（不难证明只有最小值会转移到最小值）

复杂度 。