P4690 [Ynoi2016] 镜中的昆虫

· · 题解

\tt Link

题意：区间推平，区间数颜色

这是一个非常清新的分块做法。

我们从弱化版开始谈起。

1. 区间数颜色

考虑维护每一个位置的 **上一个与其颜色相同的位置**，记为 $pre_i$。单次询问 $l,r$，就等价于求区间 $[l,r]$ 中有多少 $i$ 使得 $pre_i\lt l$。问题转化为 **求区间小于 $x$ 的数的个数**。 接下来就可以大显神通了。你可以直接主席树，也可以离线后上值域树状数组。 ## 2. 单点修改区间数颜色 ~~带修莫队？$\sout{O(n^{\frac 53})}$ 的复杂度，您想想还是算了吧~~。 考虑在第一问的解法上修改。我们维护 $nxt_i$ 代表 **下一个与其相同颜色的位置**。想想 $i$ 位置的改变会影响哪些位置。$pre_i$ 显然会被改变，$pre_{nxt_i}$ 变成 $pre_i$。 但是…怎么计算更改后的 $pre_i$ 呢？考虑维护 $n+m$ 个 `set`，记录每种颜色所有出现过的位置，这样修改暴力 在 `set` 里面 `insert()/erase()`，然后使用 `lower_bound` 来计算更改后的 $pre_i$。 因为要修改，那么主席树不行了，可以考虑 CDQ/树套树。 ## 3. 区间修改区间数颜色 乍一看，直接弃掉，这个东西没法做了。 但是你注意到一个性质：如果本来有一个区间 $[l,r]$ 颜色相同，我们要把它整体改成另一个颜色，那么只有 $prv_l$ 会发生改变（同样要变的还有这个区间右端第一个同色点），$prv_{l+1},\cdots,prv_r$ 保持不变，它们应该是 $l,l+1,\cdots,r-1$ 的一个等差数列。 既然问题和区间推平有关，这个性质和 **颜色相同的区间** 有关，那么我们来考虑一个老朋友—— $\tt ODT$，然后我们 **把所有颜色相同的区间看成一个点**。 如果我们使用上述方法对一个点进行修改，那么复杂度是不是就正确了呢？考虑证明复杂度正确。 + 首先可知一开始 $\tt ODT$ 内有 $n$ 个点。 + 每次修改 1. 把 $l$ 以及 $r+1$ 所在节点断开，一分为二。这一步最坏增加两个节点。 1. 然后删去属于这个区间的所有节点 1. 然后增加一个节点 $[l,r]$。 注意到两点 + 每次操作最坏增加三个节点（第一步两个，第三步一个），总量是 $O(m)$ 个。 + 第二步删去的节点总数是 $O(n)$ 个。 于是所有修改的总数是 $O(n+m)$。 ## 4. 区间修改怎么写 在上文有提到过维护 $n+m$ 个 `set`，记为 $t$ 数组。但是要记得维护成 $\tt ODT$ 节点的形式。 1. 我们首先提取出 $l\sim r$ 的所有 $\tt ODT$ 结点 1. 然后我们扫描 $l\sim r$ 的所有节点，把所有要修改的位置装进一个桶里 1. 注意你要修改的位置不仅仅是每个节点的左端点，还有这个节点的下一个相同值的位置（这个位置可以使用我们的 $t$ 数组进行 `lower_bound/upper_bound` 算出） 1. 删除 $t$ 里面的和 $\tt ODT$ 里面的所有这个区间内的节点 1. 最后逐一处理我们提取出来的要修改的位置，修改它。 ## 5. 单点修改区间数颜色的线性空间写法 你当然可以考虑树套树，但是 ~~我不会~~ 这题卡空间。 你当然也可以考虑 CDQ，但是个人感觉分块写法简单的多。 我们把空间限制去掉，原问题是这样的： + 单点修改 + 询问区间值 $\lt x$ 的数的个数。 这个题有一个比较显然的 序列分块+值域分块 的做法 > 注：这里的值域指的是 $prv$ 的值的范围（即 $0\sim n-1$）。在值域和 $n$ 有区别的时候，需要对于值域和序列处理两套分块辅助数组，这会比较麻烦。这题值域有特殊性质，所以考虑将其整体 $+1$，然后和序列共用一个分块辅助数组。 考虑序列分块部分在散块暴力，只想整块，那么原问题变为如此： + 单点修改 + 询问全局值 $\lt x$ 的数的个数（注意留给这一步的时间是 $O(1)$） 那么这就很简单了，它变成一个 $O(\sqrt n)$ 单点修改 $O(\sqrt n)$ 前缀（区间）和查询，直接莽上值域分块分块，这里空间是值域的 $O(n)$。 然后每个块都来一个这样的值域分块，时空都是 $O(n\sqrt n)$。 ~~然后我就在这里卡住了~~。 作为大口胡选手，我首先考虑了 Ynoi 常见套路 **离线后滚块**：对所有操作的位置进行分块，枚举块然后处理包含这个块的操作。 然后就口胡挂了，因为可能不属于这个区间的修改，也会影响到这个区间的 $prv$ 值。 然后去看 sol，发现了 [$\texttt{\color{black}Y\color{red}noi}$](https://www.luogu.com.cn/user/124721) 大佬的做法：对询问而非询问的位置进行分块，但是！！哈哈我看不懂啊哈哈哈哈！！ 于是想到此题解里区间修改的第 5 步：提取出所有要修改的位置进行修改。那么我们是不是可以把这些单点修改给存下来？（毕竟它的总数是 $O(n+m)$ 的）。 好，那就把所有的单点修改以及区间查询存下来，离线后滚块即可。 感觉这题卡不掉分块。 ## 6. [代码](https://www.luogu.com.cn/paste/bubz6le0) 总时间复杂度 $O((n+m)(\sqrt n+\log n))$，空间复杂度 $O(n)$。