题解

思路

状态转移

扫描到程序的某个位置时，设 $f_z$ 表示：在之前从未把 $x$ 赋为 $s$ 的前提下，当前 $x=z$ 的最小删除花费。不可达状态的值为正无穷。初始只有 $f_0=0$。

对于 set y v，删除它会使所有可达状态的花费增加 $v$；保留它则会把所有原状态汇聚到 $y$，花费是转移前的全局最小值。因此，若 $y\ne s$，可先对所有状态加 $v$，再用原全局最小值更新 $f_y$。若 $y=s$，这条指令必须删除，只执行全局加法。

处理条件块

进入 if y 时，只有当前值为 $y$ 的状态会执行块内指令，其余状态直接跳到块后。

因此可以从当前状态集中取出 $f_y$，把外层集合的 $y$ 位置改为正无穷，并用只包含状态 $y$ 的新集合执行块内指令。遇到对应的 end 时，将外层集合与块内集合按值逐点取最小值。这恰好合并了“跳过块”和“执行块”两类路径。

用栈保存每层外层状态集，即可迭代处理任意深度的嵌套，避免系统递归栈溢出。

做法

子任务一

当 $n\le18$ 时，枚举所有 set 指令的删除子集。对每个子集按语义模拟程序，检查是否曾把 $x$ 赋为 $s$，并对合法方案取最小花费。

设 set 行数为 $k$，时间复杂度为 $O(2^k n)$，空间复杂度为 $O(n)$。

子任务二

值域不超过 $2000$ 时，直接用数组保存所有 $f_z$。每条 set 线性扫描数组完成全局最小值、全局加法和单点更新；条件块结束时线性合并两个数组。

设值域大小为 $V$，时间复杂度为 $O(nV)$，空间复杂度为 $O(dV)$，其中 $d$ 为最大嵌套深度。

满分做法

用动态开点线段树保存有限的 $f_z$。每个结点保存区间最小值和区间加法懒标记，从而在 $O(1)$ 时间对整棵树加上花费，并在 $O(\log V)$ 时间查询或更新单个值。

条件块结束时，对两棵动态线段树做破坏式合并：若其中一棵在某区间没有结点，直接返回另一棵；否则下传标记，递归合并子区间并取最小值。每个动态结点在合并过程中只会被处理常数次。

最终所有可达终态中的最小花费就是根结点的最小值。

复杂度

每条指令最多创建 $O(\log V)$ 个结点。满分做法的总时间复杂度为 $O(n\log V)$，总空间复杂度为 $O(n\log V)$。