【题解】CF1423G Growing Flowers 题解

题意

给定一个序列，每个位置 $i$ 存在一种颜色 $a_i$ ，要求支持下列两种操作：

给定子段 $[l, r]$ 和颜色 $x$ ，将该子段所有位置的颜色全部变为 $x$ ；

给定 $k$ ，求所有长度为 $k$ 的子段内不同颜色的数量的和。
$\mathcal{Data~Range}$ ： $1 \le n, q \le 10^5$ ， $1 \le a_i \le 10^9$ ， $1 \le k \le n$ 。

题解

我们发现修改操作只有一种：子段颜色覆盖。那么我们可以考虑用 $\texttt{set}$ 维护颜色段，根据颜色段均摊，这样的时间复杂度是可以接受的。

那么现在的问题是：求出一个颜色段对答案的贡献。

乍一看，我们似乎要维护每个位置对每一种 $k$ 的贡献，时间复杂度似乎不太可以接受。

但实际上我们通过分析，可以发现贡献要么呈一段相等的数的形式，要么呈一段等差数列的形式，并且我们仅需支持单点查询，所以我们可以把贡献差分，那么询问时就仅需求前缀和即可。

接下来就是具体分析的环节。

我们钦定在段中，每种颜色第一次出现的位置才会造成实质性的贡献。

那么对于第一个位置 $pos$ ，我们考虑计算它对 $k$ 的贡献：

在包含 $pos$ 的所有长度为 $k$ 的子段中，右端点最右会延伸到 $\min(n, pos + k - 1)$ ，因为极限情况就是左端点为 $pos$ 的情况，但是右端点又不能超过 $n$ 。

假设我们现在已经维护好了 $pos$ 的颜色在 $pos$ 之前的最后一次出现的位置 $pre$ （没有则记为 $0$ ），那么在包含 $pos$ 的所有长度为 $k$ 的子段中，右端点最左会延伸到 $\max(pos, pre + k)$ ，因为极限情况就是右端点为 $pos$ 的情况，但是左端点又必须在 $pre$ 右侧（否则 $pos$ 的颜色的实质性贡献就不会由 $pos$ 提供）。

(注意 $pre$ 可以在维护颜色段的同时维护。)

综上， $pos$ 的贡献即为 $\min(n, pos + k - 1) - \max(pos, pre + k) + 1$ 。注意 $k$ 的范围为 $[1, n - pos]$ ，否则 $pos$ 会有负贡献，这是不存在的。

把贡献拆开，可以发现 $\min$ 和 $\max$ 的部分由于 $k$ 递增，所以贡献是呈一段等差数列和一段相等数列的形式的，差分后可以很方便地用线段树维护。

那么我们还需要对颜色段中 $pos$ 以后的位置做同样的分析吗？当然不需要。

我们发现，颜色段中 $pos$ 以后的位置 $pos'$ 的贡献十分简单，因为包含它的子段的左端点必须在 $pos'$ 这个位置上，所以它对所有 $k \in [1, n - pos' + 1]$ 的贡献均为 $1$ 。

稍作分析，可以发现颜色段中 $pos$ 以后的位置对 $k \in [1, n - pos]$ 的总贡献为 $\min(n - pos - k + 1, len - 1)$ （其中 $len$ 表示颜色段长度）。由于 $k$ 递增，因此这个部分的贡献仍然呈一段等差数列和一段相等数列的形式，可以继续差分后用线段树维护。