平衡树结合计数动态规划

· · 题解

Part1 前言

据说是经典题，经典题怎么能不会？

题意给定 n,A 和 Q 组限制，要求对满足每一个限制的序列 a_i\in[1,A] 计数。

每一个限制形如 l,r,w，要求 \max\limits_{i=l}^ra_i=w。

Part2 发掘性质

其实本题很开放，各种做法都可以。

我们可以逐步发掘性质，首先可以将区间离散化，转换为若干个左闭右开区间，称为元素。

我们需要将 l,r,w 转换为两个限制：

发现如果一个限制区间内有元素被要求 $\max a_i<w$，那么这个元素一定不会对该限制产生影响，可以去掉，而剩下的元素可以优先考虑本限制。 ### Part3 转换为普通计数 用 `set` 维护没有被删除的元素，将限制按 $w$ 从小到大考虑，将 $w$ 相同的限制放在一起计算，每次将被某一个区间包含的元素取出，删除。 现在问题变成了，每个元素可以染成黑（存在等于 $w$）白（全部小于 $w$）使得所有区间都包含黑色元素的方案数。 当然黑白颜色的方案数均不为一，可以默认全部都是白色，再做调整，这是一个普通计数问题。 ### Part4 解决问题 具体地，记 $f_i$ 表示第 $i$ 个元素染黑色，前面符合要求的方案数，$sf_i$ 为 $f_i$ 的前缀和。 记 $L_i$ 表示如果第 $i$ 个数染黑，上一个染黑的位置至少是多少，具体对于每一个限制 $l,r$ 让 $L_{r+1}\leftarrow\max\{L_{r+1},l\}$ 即可。 然后 $f_i=(sf_{i-1}-sf_{L_i-1})\dfrac{B_i}{W_i}$，此处，$B_i$ 表示第 $i$ 个元素然黑色的方案数，$W_i$ 表示染白色的方案数。 ### Part5 后记 该方法可能不具有普适性，但常数和简易程度较为优秀。 时间复杂度 $O(\sum Q\log(Q+M))$，空间 $O(Q)$，其中 $M$ 为模数。