题解

思路推导

每条指令只会让 $x$ 改变 $1$，因此一段执行过程访问到的整数一定构成连续区间。不同值的数量就是“最大值减最小值加一”。

令前缀和 $p_i$ 表示执行前 $i$ 条指令后的 $x$，并预处理前缀最小值、前缀最大值、后缀最小值和后缀最大值。

删除 $[l,r]$ 后，保留的前半段访问 $p_0,p_1,\ldots,p_{l-1}$。原程序后缀中的每个前缀值 $p_i\ (i\ge r)$ 会整体平移

$$p_{l-1}-p_r.$$

所以只需合并前半段的极值与平移后的后半段极值。

做法

预处理四个极值数组。对每个查询计算平移量 $d=p_{l-1}-p_r$，再令

$$L=\min(\operatorname{preMin}_{l-1},\operatorname{sufMin}_r+d),$$$$R=\max(\operatorname{preMax}_{l-1},\operatorname{sufMax}_r+d).$$

答案为 $R-L+1$。

小规模可逐查询模拟；当所有查询都删去后缀时，只剩一个前缀，直接查询前缀极差即可。独立核验程序使用前缀和稀疏表查询两个保留区间的极值。

正确性证明

删去区间前，前半段的执行状态正是 $p_0$ 到 $p_{l-1}$。删去区间后，执行后缀的起点从 $p_r$ 改为 $p_{l-1}$，所以后缀每个状态都统一增加 $p_{l-1}-p_r$。公式因此准确给出所有保留状态的最小值和最大值。

每一步只改变 $1$，从最小值走到最大值的过程中不会跳过整数，故访问集合是完整整数区间 $[L,R]$，不同值数恰为 $R-L+1$。因此每个查询答案正确。

复杂度分析

每个测试用例预处理 $O(n)$，每个查询 $O(1)$；总时间复杂度为 $O(\sum n+\sum m)$，空间复杂度为 $O(n)$。