自动搬运

查看原文

来自洛谷，原作者为

	EnofTaiPeople MGXS

搬运于2025-08-24 21:57:53，当前版本为作者最后更新于2023-03-15 07:42:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Part1 前言

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

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

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

Part2 发掘性质

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

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

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

$\forall i\in[l,r],a_i\le w,\exists i\in[l,r],a_i=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$ 为模数。