ARC204A Use Udon Coupon
Iniaugoty
·
·
题解
注意到维护的 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)。
代码。