区间数颜色

2026-04-22 21:51:40

发布于：广东

28阅读

0回复

0点赞

为方便表示时间复杂度，假设 $n,q$ 同阶。

不带修：P1972

Difficulty：4.1 / Easy

定义 $\text{next}_i$ 为 $i$ 相同颜色的后继，即最小的 $j$ 满足 $j\gt i,A_j=A_i$ 。显然可以 $O(n)$ 求出。

定义 $\text{pre}_i$ 为 $i$ 相同颜色的前继，即最大的 $j$ 满足 $j\lt i,A_j=A_i$ 。显然可以 $O(n)$ 求出。

考虑 $l$ 固定后， $r$ 往右移动 $1$ 格后会怎么样。显然：

定义 $c_{l,r}$ 为区间左端点为 $l$ ，由 $r-1$ 移动到 $r$ 的贡献。

注意到 $c_l$ 与 $c_{l+1}$ 的差距只在于 $c_{l,l}$ 从 $0$ 变成 $1$ 与 $A_{\text{next}_i}$ 从 $1$ 变成 $0$ 了。

我们可以主席树实现或者扫描线动态维护 $c$ 。

$O(n\log n)$ 。

Difficulty：4.7 / Easy

考虑修改会产生什么影响。

显然，就是修改了 $O(1)$ 个位置的 $\text{next}$ 。

而每次修改 $\text{next}_i$ 会给后面的查询中，区间与 $[i,\text{next}_i]$ 有左交集并且与 $[\text{pre}_i,i]$ 有右交集的答案产生 $1$ 的影响。

哦，这下看懂了。

CDQ 分治即可。

$O(n\log^2 n)$ ，代码有时间再写。

Difficulty：4.8 / Easy

注意到修改 $[l,r]$ 后， $l\le i\lt r$ 的 $\text{next}$ 会变成 $i+1$ ，其余的只有 $\text{pre}_l$ 和 $r$ 的 $\text{next}$ 会改变。

假设已经修改了 $[l_1,r_1]$ 并且没被动过，现在要修改 $[l_2,r_2]$ 。我们可以发现 $[l_1,r_1)$ 与 $[l_2,r_2)$ 的交集的 $\text{next}$ 不会改变。

所以有一个结论，修改 $q$ 次后 $\text{next}$ 的总修改次数不超过 $O(n+q)$ 。

所以可以和上面一样，CDQ 分治即可。

$O(n\log^2 n)$ ，代码有时间再写。

有帮助，赞一个

去预览

0/2000