ARC204A Use Udon Coupon

注意到维护的 $Q$ 事实上是一个队列，那么这个条件可以先转化成，将 $A$ 和 $B$ 归并，要求操作序列的每一个前缀中 $A$ 的数量都不少于 $B$ 的数量。

这个跟括号序列一样的玩意儿典到家了。我们考虑一条折线状物，最初在点 $(0, 0)$，若当前遇到 $B$，则向右走 $B_i$，向上走 $B_i$；若当前遇到 $A$，则向右走 $A_i$，向下走 $A_i$，同时，过程中如果达到 $y = 0$，就保持在这条线上水平向右，而并非向下，这对应了与 $0$ 取 $\max$。设 $S = \sum _ {1 \le i \le n} B_i - \sum _ {1 \le i \le n} A_i$，那么我们最后会到达 $(S, S + k)$ 的位置。

至于为何会有这个 $+k$，显然是中途产生了一些与 $0$ 取 $\max$ 导致的。问题进一步地转化成了 $k \le R - S$ 和 $k \le L - 1 - S$ 的操作序列数量。

考虑 $k$ 是啥。我们先不与 $0$ 取 $\max$，折线最后会跑到 $(S, S)$ 的位置，中途会在 $y = 0$ 以下有一部分。考虑某个这样的点 $(x_0, y_0)$，我们从第一象限走到第二象限来到 $(x_0, y_0)$，再和 $0$ 取一个 $\max$，这时相当于将 $x_0$ 右边的整个折线都向上平移了 $\lvert y_0 \rvert$。遍历每一个这样的最低点，直到整个折线都平移到了第一象限，总共平移的距离 $k$ 显然是最低点的纵坐标绝对值，也即前缀 $\sum A - \sum B$ 的 $\max$。

已经差不多了。问题最后转化成了，对于 $x \in \{ L - 1 - S, R - S \}$，求出 $A$ 和 $B$ 归并起来的序列个数，满足：

直接对着这个东西计数即可，设 $f _ {i, j}$ 表示考虑到 $A_i$，在其之前有 $j$ 个 $B$ 的方案数。第一个条件限制了 $j < i$，第二个条件限制了 $j \ge p$，其中 $p$ 是最小的满足 $\sum _ {1 \le k \le i} A_k - \sum _ {1 \le k \le p} B_k \le x$。枚举 $A _ {i - 1}$ 与 $A_i$ 之间 $B$ 的个数，从 $f _ {i - 1, ?}$ 转移到 $f _ {i, j}$，直接做是 $O(n ^ 3)$ 的，容易使用前缀和或双指针做到 $O(n ^ 2)$。

代码。