高维问题

参考了 dead_X 老师了的课件。

Part 1.扫描线

扫描线的核心思路就是将一个序列维转换为一个时间维，然后枚举这个时间维从而达到降维的效果。

而剩余的维度我们就可以使用其他的数据结构来维护。

但是使用扫描线有一个严苛的要求:原问题中的询问和时间不相关。

例题1：P10814 【模板】离线二维数点

我们可以把 \(a_i\) 看成一个点 \((i,a_i)\)。

那么我们现在的问题就转化为：在右上角为 \((r,x)\)，左下角为 \((l,0)\) 的矩阵中有多少个点。

此时我们可以将这个问题转化为在右上角为 \((r,x)\)，左下角为 \((0,0)\) 的矩阵中点的个数减去在右上角为 \((l-1,x)\)，左下角为 \((0,0)\) 的矩阵中的点的个数。

那么我们在本题当中可以将横坐标作为时间维，然后用树状数组来维护目前 \(\le x\) 的数的个数。

例题2: P8421 [THUPC2022 决赛] rsraogps

和上一题类似的，我们以 \(r\) 为时间轴，然后记 \(s_i\) \(i = L,R \le r\) 的区间 \([L,R]\) 的答案之和。那么问题就变成了怎么维护 \(s_i\)。

我们考虑 \(A_i,B_i,C_i\) 的变化：

• \(A_i\) 的二进制中 \(1\) 会变成 \(0\)。

• \(B_i\) 的二进制中 \(0\) 会变成 \(1\)。

• \(C_i\) 的因数会逐渐减小。

然而我们发现这种减小最多只会改变 \(O(\log n)\) 次，那么我们就可以暴力维护这三个值了。

Part 2.CDQ分治

我们可以利用分治剪掉一维！

我们可以先处理左边和右边的贡献，然后再考虑左右两边之间的贡献即可。

具体的先处理所有 \(l \le i,j \le mid\) 的点对然后在考虑 \(mid + 1 \le i,j \le r\) 的点对数量，最后再考虑 \(1 \le i \le mid\) 且 \(mid + 1 \le j \le r\) 的点对数量即可。

例题1: P9068 [Ynoi Easy Round 2022] 超人机械 TEST_95

对于每一个值 \(i\) 我们可以维护 \(x_i\) 表示第一次出现的位置和 \(y_i\) 表示最后一次出现的位置。

那么我们现在要求的就是 \(\sum_{i,j} [x_i < y_j][i > j]\)。

然而我们发现一次修改操作最多只会修改 \(2\) 个 \(x_i\) 和 \(2\) 个 \(y_i\)。那么我们只需要单点修改就行了。

你以为这就结束了吗？

不，CDQ 分治还可以将带修改的问题转化为静态问题。

对于这种东西我们可以把所有的操作离线下来，然后在时间为上进行 CDQ 分治。

而这里我们会有贡献的点对就是一个修改和一个查询的答案。

例题2: P4690 [Ynoi2016] 镜子里的昆虫

维护每个位置左侧第一个同色点的位置，记 \(pre_{i}\)。此时区间数颜色就被转化为了一个经典的二维数点问题。

可以证明 \(pre\) 只会变化 \(O(n + m)\) 次，即单次操作只会导致 \(O(1)\) 个 \(pre\) 值变化。那么我们可以用 CDQ 分治来解决动态的单点加矩形求和问题。

然后 \(pre\) 直接用 ODT 来维护就可以了。

Part 3：线段树分治

考虑如何动态维护一个图，并且查询他是否为一个二分图。

考虑用线段树维护时间轴，把边挂在线段树对应的节点上。然后遍历线段树，然后线段树上的节点维护在图上相对应的节点的可撤销并查集。进去该节点时加入边对并查集的影响，出去时撤销即可。

此时时间复杂度为 \(O(n \log^2 n)\)。

例题1：Painting Edges

看到这种题考虑线段树分治。

对于每一个颜色 \(k\) 我们都开一个可撤销并查集，然是我们发现将判断和区间操作放在一起比较难做，于是考虑把判断和区间操作分开进行。

区间操作其实就是，对于一条边的两次染色 \(x,y\)，染色区间为 \([x+1,y−1]\)，颜色有两种可能：

• 染上去了，颜色是 \(x\) 染色时的颜色。

• 没染上去，颜色是上一次染色的颜色。

那么判断变成单点问题了，分治的时候直接判断即可。