【数据结构】降维技巧

通过降维度，可以将高维问题转化为低维问题，从而优化复杂度。

偏序类降维

在高维偏序中，如果各个偏序变量之间有一定相关性，那么可能可以利用相关性降维。

TEST_73

给定一棵树，点和边各自有编号。$m$ 次询问只保留编号在 $[l,r]$ 中的点，以及编号在 $[l,r]$ 中的边后，联通块的数量。【此时 $a,b$ 联通相当于它们之间的简单路径经过的点和边都 $\in [l,r]$。】 $n,m\le {10}^6$。

Solution: 考虑对于一个森林，若点的数量为 $n$，边的数量为 $m$，那么联通块的数量即为 $n-m$。

接下来我们要求出只保留询问限制时的点边数量。点数自然为 $r-l+1$。而一条边满足询问限制，当且仅当其两端点的点（不妨设它们为 $x,y$ 满足 $x<y$）编号都 $\in [l,r]$，且这条边的编号（不妨设其为 $u$）$\in [l,r]$。

这是三维限制：

$$x\ge l\wedge y\le r\wedge u\in [l,r]$$

但是，我们发现由于点和边的限制区间都是一样的，所以实际上它可以转为：

$$min(x,u)\ge l\wedge max(y,u)\le r$$

这样子就被我们降了一维，转化成了二维偏序问题。

常数种斜率的降维

实际上是偏序降维的特殊情况。

某题

给定 $n$ 个区间 $[l^{\prime },r^{\prime }]$，$m$ 次询问，每次给定 $l,r,k$，求有多少给定的区间满足其被 $[l,r]$ 包含，且长度 $\ge k$。

首先判掉 $r-l+1<k$ 的情况。然后我们考虑扫描线枚举 $k$ 这一维，剩下的是一个动态二维限制问题，但是这里有个比较智慧的想法：

$(\sum [r^{\prime }\le r])-(\sum [l^{\prime }\le l])$ 即为答案。

证明考虑：（以下黑线为询问区间，蓝线为给定 $n$ 区间中的某个）

这两种情况对上式有 $0$ 的贡献。（左右两项都有贡献）

此时对上式有 $1$ 的贡献。（左边一项有 $1$ 的贡献，右边没有）

这两种情况对上式有 $0$ 的贡献。（左右两项都没有贡献）

而不存在蓝线包含黑线（严格包含，蓝线不等于黑线）的情况，因为我们把 $r-l+1<k$ 判掉了，于是扫描线枚举 $k$ 时，加入的蓝色区间都刚好被这个限制限制住了，无法使得蓝线包含黑线。

然后，我们两种“动态一维数点”分别做即可。

上述想法有点 Ad-hoc 了，我们来考察它的本质是什么。

在二维平面上，查询三角形区域内点数：

【暂未完成】

TEST_139

三角形加，矩形权值和。

「差分不会亏！」

折线类降维

如果贡献构成折线（阶梯型），即区间互相不包含，则可能利用这一点降维

某题

给你 $n$ 个区间 $[l^{\prime },r^{\prime }]$，这些区间两两不互相包含，每个区间有权值。
$m$ 次查询，每次给定 $l,r,k$。求最大权值的区间 $[l^{\prime },r^{\prime }]$ 满足其在 $[l,r]$ 内，并且长度 $\ge k$。

区间不包含启示我们按左端点排序，那么此时右端点也是有序的。

于是询问的限制便可以转化成对“区间序列”的区间编号 $\in [l,r]$。可以简单通过二分或者类似的东西实现。

然后 $k$ 从大往小扫描一下，维护单点修改，区间 max 即可。

P9061 弱化

你需要维护一个平面，初始有 n 个点 (x’,y’)

1. 给定 x,y，将所有 x’<=x 且 y’<=y 的点删除
2. 查询一个矩形的和
   n,m<=2e6

【暂未完成】

P8337 弱化

给定 $n$ 个区间 $[l^{\prime },r^{\prime }]$，这些区间保证互相不包含有 $m$ 次查询，每次查询给定 $[l,r]$，求 $[l,r]$ 和所有满足 $r^{\prime }\in [l,r]$ 中的 $[l^{\prime },r^{\prime }]$ 的交的长度的和
$n,m\le 2\times {10}^7$

继续考虑排个序，然后对于 $l^{\prime }<l$，维护 $r^{\prime }$ 的一次和以及零次和（即出现次数），一次和减去出现次数乘上 $l$ 即为这部分长度。

考虑被完全包含的部分。我们发现，可以在询问区间中找到一个分解点，使得左边都是上述情况，右边都是完全包含。

找到分界点之后直接求区间和即可。现在的问题是怎么求分界点。

【暂未完成】

支配降维

最值问题不能差分，但是可以利用支配关系，适当放宽维护的条件。

举个例子，就是若合法情况可以支配一部分不合法情况，就可以不用考虑把这部分不合法情况剔除。

P11210

【暂未完成】