2020 CCPC 网络选拔赛 A Art Class

发表于 2020-12-21 更新于 2023-12-05 分类于数据结构，线段树阅读次数：

题面

依次将 $n$ 个下边界在 $x$ 轴上的矩形涂黑，求每次涂色后总图形的周长。

其中 $1 \le n \le 2 \times 10^5$。

分析

横线部分就是线段覆盖，这是平凡的。

竖线部分，更新操作就是区间取 $\max$，对于线段树节点 $[l,r]$，需要维护 $\sum_{i=l}^{r-1} |a_{i}-a_{i+1}|$。

考虑 Segment Tree Beats，我们在线段树节点维护了区间最小值和区间次小值。当最大值更新为 $x$，$x$ 小于节点次大值，将区间内所有最小值提升为 $x$，可以发现这个过程中改变的是最小值和相邻高点之间的差。因此，我们对于一个线段树节点区间，维护所有相邻的是否是最小值导致间断点，假设我们维护了这样的间断点个数，那么对于区间答案的容易进行更新。

间断点的个数容易维护，首先它可能从左右子树上传得到，然后在考虑将左右区间拼接点的贡献即可。

最后，注意我们区间覆盖最小值时打的标记，也包含了懒标记效果，记得下传信息。注意维护次小值的细节。

阅读全文 »

2021 Byte Camp 2021 Qualification Round M Expected area 题解

发表于 2020-12-20 更新于 2023-12-05 分类于题解阅读次数：

题面

给定 $2n$ 个线段 $[l_i,r_i]$ $(1 \le i \le n)$ 和 $[s_i,t_i]$ $(1 \le i \le n)$，对于所有排列 $p$ 求 $\bigcup_{i=1}^{n} [l_i,r_i] \times [s_{p_i}, t_{p_i}]$ （面积并）之和。其中 $1 \le n \le 2 \times 10^5$。

分析

拆开来算贡献。

对于第一维（$x$ 轴），将其通过左闭右开区间离散化为小块。假设每块被覆盖了 $s_i$ 次，也就意味着这一个块对应了 $s_i$ 个 $y$ 轴线段。比如说，$s_i=0$，那么上面没有任何线段；$s_i=1$，对应了 $1$ 个线段，也就是所有线段均有可能竖着放在它上面，对答案的总贡献为所有线段的总长度；类似地，$s_i=2$ 就是枚举一对线段计算贡献之和。

可以发现，对于每一个小块只有参数 $s_i$ 有效。于是，我们将问题转化为了一个一维的问题，即对于从线段集合中选择 $k=0,1,\dots,n$ 条线段产生的总贡献，形式化地 $f(k)=\sum_{S \subseteq U, |S|=k} |\bigcup_{i \in S} [s_i, t_i]|$。

再拆开来算一次贡献，同样离散化。假设每块被覆盖了 $s_i$ 次，这个块产生贡献当且仅当选出的 $k$ 个块包含 $s_i$ 中的某一个，即方案数就是 $\binom{n}{k} - \binom{n-s_i}{k}$，对于贡献还要乘上块的长度。观察上面的式子，第一部分是平凡的，关键是第二部分，因为我们最终计算的是 $f(k)$ 每个点的值，因此同样的 $n-s_i$ 产生的长度贡献可以记录在一起。于是，我们定义这部分的贡献函数 $g(k)=\sum_{i=k}^n a_i C(i,k)$，其中 $a_i$ 就是长度和。

将 $g$ 展开

$$
\begin{eqnarray}
g(k) & = & \sum_{i = k}^n a_i \frac{i!}{k!(i-k)!} \
g(k) & = & \frac{1}{k!} \sum_{i = k}^{n} (a_i \cdot i!) \times \frac{1}{(i-k)!}
\end{eqnarray}
$$

注意到上式的下标分别为 $i$ 和 $i-k$，即差为定值 $k$，使用 FFT 计算即可。

最后，还有一点小问题，$f(k)$ 的贡献是无序的。它表示从第二个集合中选择了 $k$ 条线段去和横轴某一小块的 $k$ 次覆盖对应，剩余随便，也就是需要乘上两部分内部的排列，即 $k! \times (n-k)!$。

阅读全文 »