浅谈一类覆盖与遍历问题

我们现在有一个数列，初始全为 0。每次进行一个区间覆盖，求最后的序列。

单 \log 显然是容易的，但是有没有更快的做法呢？

考虑倒序处理，这样我们把覆盖问题变成了遍历问题，问题就类似于求的是将这个序列每次选择一个区间进行遍历，最后问每个数是第几次遍历到的。

这个问题可以简单地用并查集维护，你可以看上一篇文章的最后一块，O(n\alpha(n))，你甚至还可以线性序列并查集一下做到 O(n)，不过我并不是很会这个东西，所以不表。

现在，如果这个问题扩展到二维了，我们该怎么办？

答案是这道题根本做不了优于双 \log。

不过，对于一些特殊的情况，我们会有一些特殊的处理方式。

问题如下：

我们现在有一个矩阵，初始全为 0。每次进行一个前缀矩阵覆盖，求最后的矩阵。

然而由于矩阵可能很大，所以我们每次询问一些点，求这些点的值。

树套树容易做到双 \log，但是有没有更快的做法呢？

还是倒序转成遍历，我们注意到点数是 O(n) 的。

那么我们肯定可以转化成一个序列，然后就类似于将 i 前面且 a_i<a_j 的点遍历，每个元素有一个遍历顺序，

这里有三种做法，主席树，CDQ 分治，还有线段树配合 set。

先说说主席树。考虑直接顺着序列枚举下去，每次你相当于对一个版本的线段树进行一个区间遍历，这个可以直接再倒序回来然后线段树，也可以并查集不过就没有任何意义了，因为可持久化并查集和主席树复杂度一样，然后再把现在遍历到的新点插入到一个新的版本的线段树就行了。

再说说 CDQ，对最开始那个序列分治下去，统一处理 [l,mid] 到 [mid+1,r] 的边。对 [l,r] 中出现的权值从小到大排序，然后建立虚点。对于左半边，将虚点连向对应的真实点，对于右半边，将真实点连向对应的虚点，然后遍历这个新图一遍就行了。

最后说说线段树配合 set，常数最小，甚至空间线性。假如我们现在遍历到第 i 个点，我们事实上只需要找到在他左边中没遍历过的最小的 a_i 就行，容易使用线段树，对于每一个底层节点存一个 set，每次遍历时加入或擦掉一个点，同时在线段树更新即可，推荐使用 zkw 线段树。

例题是这道，建图，做费用流，你会发现边太多了，用任意一种优化即可。