ARC204A - Use Udon Coupon 笔记

膜拜 larsr。

先差分，设 $f(x)$ 表示 $C\in [0,x]$ 的方案数，原问题等价于 $f(R)-f(L-1)$。

有个 trick，假设确定了操作序列，那么假如 $C^{\prime }$ 没有 $max(0,C)$ 的限制，求 $C=x$ 的方案数，就相当于求 $C=C_{\mathrm{最}\mathrm{终}}^{\prime }-\underset{\mathrm{操}\mathrm{作}\mathrm{中}\mathrm{的}\mathrm{任}\mathrm{意}\mathrm{时}\mathrm{刻}}{min}{C}^{\prime }$（注意 $min$ 出来是负数），因为就相当于在 $min{C}^{\prime }$ 那里 $C$ 变成了 $0$，那一部分的负数不应该进入 $C$，而 $C_{\mathrm{最}\mathrm{终}}^{\prime }$ 实则是 $(\sum B)-(\sum A)$，记作 $S$。

现在要求 $C\le x$，就相当于求 $-min{C}^{\prime }\le x-S$，即 $max-C^{\prime }\le x-S$，然后 $max-C^{\prime }=\underset{i,j}{max}((\sum _{[1,i]}A)-(\sum _{[1,j]}B))$，那么只需要保证转移中的每一对 $\{i,j\}$ 都满足条件即可。

前缀和处理一下 $A,B$，设 $f_{i,j}$ 表示 $A,B$ 取到 $\{i,j\}$ 且合法的方案数，其中 $f_{0,0}=1$，答案为 $f_{n,n}$，显然若 $\{i-1,j\}$ 对 $\{i,j\}$ 合法则 $\{i-1,[1,j]\}$ 合法，所以让 $f_{i,j}$ 从 $f_{i-1,j}$ 转移过来，最后对 $f_i$ 做个前缀和即可。

时空复杂度 $O(n^2)$。