题解

思路

令 $dp_i(x)$ 表示前 $i$ 个位置合法且 $X_i=x$ 的方案数，$S_i=\sum_x dp_i(x)$。

做法

加入上界 $A_{i+1}$ 后，有 $dp_{i+1}(x)=S_i-dp_i(x)$（$x\le A_{i+1}$），其余位置为零。所有可能的 $x$ 上，$dp_i(x)$ 始终是若干连续区间上的常值函数；每一步先把定义域截到 $A_{i+1}$，再对保留区间统一执行 $y\mapsto S_i-y$，若定义域变长，新增部分的值为 $S_i$。

用栈记录这些常值段的长度和基准值，并用一个全局符号与偏移量懒惰表示所有段共同经历的仿射变换。定义域缩小时，每个段至多被弹出一次；变长时只增加一个段，因此总操作次数为 $O(N)$。同时维护各段值乘长度之和即可得到新的 $S_i=A_{i+1}S_{i-1}-\sum_{x\le A_{i+1}}dp_i(x)$。

复杂度

时间复杂度为 $O(N)$，空间复杂度为 $O(N)$。