AGC041F
lsj2009
·
·
题解
Preface
非常 Educational 的题！
虽然感觉独立做出了大半，但还是感觉这个题很深刻。
Description
给定一个直方图，其中第 i 列高度为 a_i，可以往上面放若干个車，每个車会占领其 所在列上的所有格子 和 向左、向右延申直到碰到边界的所有格子。
求有多少种放車的方案使得每个位置都会被 至少一个 車占领。
**Bonus：**$1\le n\le 3000$，$1\le a_i\le 10^9$。
## Solution
### Part 1
事实上相当于每个位置上有一个限制，刻画为：所在行的连续段和所在列至少有一个車。
则答案就是对于满足每个限制的方案集合 **交集**，也就是得满足所有限制。
比较套路地，钦定 $i$ 个限制 **违反**，其于限制 **不进行强制要求**，只需要将此情况的方案数乘上 $(-1)^i$ 再求和即可。
容斥系数推导较为经典，这里不赘述。
若枚举所有 **钦定违反限制的格子集合** $S$，是容易快速计算出此情况下的方案数的，即可做到 $\widetilde{\mathcal{O}}(2^{\sum a_i})$ 复杂度。
### Part 2
一个关键观察是：**列是连续的**。
所以考虑 **枚举**（注意不是钦定！！这会在全文的最后有解释）哪几列 **存在我们钦定违反限制的格子**。记我们枚举的列集合为 $S$。
这里 **枚举** 的含义是：任意 $x\in S$ 的列均存在钦定违反限制格子，任意 $x\notin S$ 的列均不存在钦定违反限制的格子。
则每一行，会分成若干连续段 $[l_1,r_1],[l_2,r_2],\cdots,[l_k,r_k]$，对于每一个连续段考虑其是否存在不合法格子。
- 不存在：则任意 $x\notin S$ 的列均可以放車，对答案贡献即为 $2^{|[l_i,r_i]|-|[l_i,r_i]\cap S|}$。
- 存在：则该连续段内不可以放車，且需在 $[l_i,r_i]\cap S$ 内选择一 **非空** 子集 $T$ 钦定 $T$ 中所有格子违反限制，即对答案贡献为 $\sum\limits_{\emptyset\ne T\subseteq \left([l_i,r_i]\cap S\right)} (-1)^{|T|}=\left(\sum\limits_{i\ge 0} \binom{|[l_i,r_i]\cap S|}{i}(-1)^i\right)-1=-[[l_i,r_i]\cap S\ne\emptyset]$。
记 $t=|[l_i,r_i]\cap S|$，则该连续段对答案贡献为 $2^{|[l_i,r_i]|-x}-[x\ne 0]$。这里的贡献为 **乘法**。
然而你注意到这样子其实不太对：
- 任意 $x\in S$ 的列 **均存在** 钦定违反限制格子。
- 任意 $x\notin S$ 的列 **均不存在** 钦定违反限制的格子。
我们并没有保证前者的每一列都存在违反限制的格子。
但这仔细看这句话：**任意** $x\in S$ 的列 **均存在** 钦定违反限制格子。
这其实对于每个 $x\in S$ 都是一个限制，我们求的就是对于每个满足限制的方案集合 **交集** 的大小。
这其实和我们最开始的问题形式上一模一样！！！
同样考虑容斥，钦定一个列集合 $T\subseteq S$，令任意 $x\in T$ 的列 $x$ 违反限制，也就是其中 **没有** 违反限制的格子（但仍然 **不能放車**，否则这和我们枚举集合 $S$ 的根本冲突了！）。同样，带 $(-1)^{|T|}$ 的容斥系数即可。
则原来的贡献改写成如下形式：
- 不存在：则任意 $x\notin S$ 的列均可以放車，对答案贡献即为 $2^{|[l_i,r_i]|-|[l_i,r_i]\cap S|}$。
- 存在：则该连续段内不可以放車，且需在 $[l_i,r_i]\cap (S\setminus T)$ 内选择一 **非空** 子集 $T'$ 钦定 $T'$ 中所有格子违反限制，即对答案贡献为 $=-[[l_i,r_i]\cap (S\setminus T)\ne\emptyset]$。
这样子暴力做我们也就获得了一个 $\widetilde{\mathcal{O}}(3^n)$ 的做法。
### Part 3
进一步优化：我们考虑将整个直方图 **剖分**。
这也就是我们上面说的每一行的连续段，当然我们有把这种“比较厚”的连续段缩在了一大块。
如何比较好的刻画这个东西？**广义笛卡尔树**（这个东西在网上好像没有什么 blog，但确实是有听过这样子的一个名字的）。
普通的笛卡尔树是一个二叉树，且仅在对 **排列** 建树时有比较好的定义，否则如果当前 **存在多个最值**，取谁为根是要打一个问号的。
广义笛卡尔树给出了比较好的解决方法。广义笛卡尔树上分 **方点** 和 **圆点**，前者刻画为一个 **区间**，后者为一个 **单独的点**。
下面给出一个例子可能可以比较好的解释：
- 求序列 $1,1,4,5,1,4$ 的广义笛卡尔树。
这应该就很清晰了。
注意到对于一个行段算贡献的时候我们其实只关心 $|S\cap[l_i,r_i]|$ 的值和 $[(S\setminus T)\cap[l_i,r_i]=\emptyset]$ 的值。
考虑在 $a$ 序列的广义笛卡尔树上 dp。更清晰的，对于一个广义笛卡尔树上的方点（这对应一个连续段）的区间 $[l_i,r_i]$ 我们 **暂且先仅保留 $S$ 在 $[l_i,r_i]$ 中的部分**，记录 $|S|$，以及当前是否有 $S\setminus T=\emptyset\Rightarrow S=T$。
合并两个儿子时对于 $|S|$ 做加法，$[S=T]$ 取与即可。
即：
$$
f_{u,i,p_1}\times f_{v,j,p_2} \to f'_{u,i+j,p_1\operatorname{and}p_2}
$$
进行完子树内的合并后考虑 **连续段内产生的贡献**：
$$
f_{u,i,p}\times\left(2^{|[l_u,r_u]|-i}-(1-p)\right)^{b_u}\to f_{u,i,p}
$$
其中 $b_u$ 为该方点和其父亲节点 $a$ 值之差，也就是该连续段的 **厚度**。
核心在于：对于一个节点 $u$ 的两个儿子，**其对应区间无交**。
圆点有何用？初始化 $(-1)^{|T|}$ 的系数。
$$
\begin{aligned}
& f_{u,0,1}=f_{u,1,0}=1\\
& f_{u,1,1}=-1
\end{aligned}
$$
由于转移需要快速幂，所以复杂度即为 $\mathcal{O}(n^2\log{V})$。
## Code
[Submission Link](https://atcoder.jp/contests/agc041/submissions/60911882)。
## Others
这时候再来回头看看为啥 $S$ 是 **枚举**。
**钦定** 表示为强制令 $S$ 中的每一列均存在违反限制的格子，而不在 $S$ 中的列是不进行约束的（这样就导致了 **钦定** 往往带有额外的容斥系数）。
但其实注意到 **不进行约束** 的方案数是很难计算的，因为你无法很好地计算 **既可以有违反格子也可以无违反格子** 的方案数。
所以我们强制钦定不在 $S$ 中的列均不能有违反的格子，这样子也就能快速算方案数了。