省选-数据结构-离线思想

很多时候，一道题在线是很难做出来的，我们可能需要离线的思想。

（虽然有时候在线能做，也可以用离线。而且很多时候在线的部分分也有离线）。

离线常见思想：

• 对于维度进行操作，将时间维度用数据结构维护。（e.g. 扫描线）
• 将答案整体进行差分，对于 $i$ 的答案就是前面所有修改的变化量的和。
• 对多个查询，只计算一次其公共部分。（e.g. 整体二分，莫队）
• 询问互相影响，将询问统一求解。（e.g. CDQ 分治）
• 维护同一时间内的信息（e.g. 线段树分治）

发现了一篇好的文章，之后有空了一定要读一下：许昊然《浅谈数据结构题几个非经典解法》。

扫描线

扫描线的离线思想：一个问题有多个维度，我们可以离线处理一个维度，数据结构维护另一个维度。

这里面有我扫描线的总结，含例题。

P5490 【模板】扫描线 & 矩形面积并

P5490 【模板】扫描线 & 矩形面积并。

这道题并没有对于离线的转化，只是有助于理解扫描线的思路。

我们按照 $y$ 轴从下往上扫，我们存出每个矩形的上下界，就会发现这些之间，连续的一段被覆盖的 $x$ 的位置都是相同的，所以我们只需要维护这一段 $x$ 的长度，再乘上 $y$ 就是面积了。

P8518 [IOI 2021] 分糖果

P8518 [IOI 2021] 分糖果。

这道题有点复杂，这里重点讲怎么对时间维度转化的。

题目是对一个数的值设定了上下限 $c$，然后有单点加减 $v$ 和最后的询问所有的值。

题解里面总结出了一种思想：将序列维度和时间维度交换，也就是我们扫描序列，维护时间这个维度的信息。

这道题就是扫描糖果序列，我们知道的是某个区间有糖果，所以扫描线 $l$ 加入，$r+1$ 删除，这样我们就能知道当前糖果经历了什么操作。然后时间就是我们要维护的用来查询的东西。

然后这道题我们就是维护在时间线中的一些东西，具体的放在这里不重要，所以折叠了。

所以很多时候需要将时间这个维度放入考虑范围，相当于一维的题目看成二维。

差分询问

我感觉这个东西其实就是扫描线的一部分吧，只是我想单独拿出来。

有的时候题目好像每个询问都要输出答案，但是这也能离线。“在所有操作之后输出结果”是经典的离线问题，有这句话几乎意味着在线不可做，我们需要离线下来。

我们发现一个修改会对之后所有的有影响，所以可以差分。我们自定义按照一个维度排序，需要保证按照这个处理顺序，不同维度之间不会互相影响。

P5526 [Ynoi2012] 惊惶的 SCOI2016

P5526 [Ynoi2012] 惊惶的 SCOI2016。
CF1172E Nauuo and ODT。

这是我的总结第三遍引用这道题。

这道题也用到了这种离线的思想，就是当前修改会对后面的产生多大的影响，差分下来。

我们发现对于每种颜色，其他颜色不会干扰自己，所以我们可以一个一个颜色处理，然后这个颜色的这个询问会对它的时间的答案做出的变化放进差分数组，最后统一处理。

具体思路在我扫描线的总结里面。

线段树分治

我认为线段树分治有是一种不同的思想了。扫描线是将 $l$ 加入，$r+1$ 删除，但是线段树分治维护的是不可差分的信息，也就是没办法这样直接删除维护的信息。

所以我们就需要利用栈的撤销来维护了。我们联想到了线段树的分治思想，对于每一个点的区间，我们可以维护哪些询问或修改是包含了这个区间的，如果包含了，那这个区间就需要进行询问的处理。处理询问的时候，我们无论如何，都需要撤销掉当前点所有的修改，因为如果保留，之后就没办法撤销了。这样的话，我们就用分治的复杂度做完了无法差分的题目。

比如说来看一下模板题：

P5787 【模板】线段树分治 / 二分图

P5787 【模板】线段树分治 / 二分图。

有 $m$ 条连接 $x,y$ 的边在 $l$ 时刻出现 $r$ 时刻消失。输出在第 $i$ 时间段内这个图是否是二分图。

二分图可以用并查集判断。但是我们发现我们不能凭空撤销一条边，这会严重影响结构，因为存在多次合并，我们无法直接知道原本的值。

然后我们就需要维护每个点的并查集，这个并查集我们只需要用可撤销并查集，然后配合上刚刚的线段树分治就行了。

void query(int x,int l,int r){
	int pd=1;
	int lt=top;
	for(edge i:t[x]){
		int a=i.u,b=i.v;
		int fa=find(a),fb=find(b);
		if(fa==fb){
			for(int j=l;j<=r;j++)puts("No");
			pd=0;
			break;
		}
		add(a,b+n);
		add(b,a+n);
	}
	if(pd){
		if(l==r)puts("Yes");
		else{
			int mid=l+r>>1;
			query(ls,l,mid);
			query(rs,mid+1,r);
		}
	}
	while(top>lt){
		sz[f[st[top]]]-=ad[top];
		f[st[top]]=st[top];
		
		top--;
	}
}

cdq 分治

没错，就是天天和各种数据结构对着干的那位，基础总结，只有模板。

离线算法的常见思路包括将询问统一求解（如 CDQ 分治）、通过一个询问的答案求出另外相似询问的答案（如 整体二分 和 莫队算法）等．——OI Wiki

cdq 本身其实不完全算数据结构，但是由于它能离线处理很多数据结构处理的偏序问题，所以经常被放在数据结构这里面讲。其实这不完全算是离线思想，只是这是偏序问题的离线解决方案。

很多时候，我们可以把一道题转化成偏序问题，然后不管是用 cdq 还是数据结构都可以处理。

最基础的就比如是逆序对这种问题，然后进阶一点的话就会把各种维度转换成偏序，比如时间转换成偏序，因为前面的会影响后面的，所以有的操作生效的前提是 $t_i<t_j$ 这种。下面的就是一道待修的例题，包含时间转换成偏序的思想。

整体二分

之前没写过整体二分的总结，就放这里了。

可以使用整体二分解决的题目需要满足以下性质：

询问的答案具有可二分性

修改对判定答案的贡献互相独立，修改之间互不影响效果

修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值

贡献满足交换律，结合律，具有可加性

题目允许使用离线算法

——许昊然《浅谈数据结构题几个非经典解法》

我觉得整体二分的思想就是有一堆询问，我们如果一个一个处理，就会浪费很多资源，所以我们可以放一起，需要共同计算的就一起先计算了，再分开。

整体二分是比如我们对于 $mid$，我们统一将 $[l,mid]$ 的数据存进去，然后每一个问题进行查询需要放左边还是右边，把一些答案 $>mid$ 的放右边，$\le mid$ 的放左边，递归处理。

如果是普通的二分，$[l,mid]$ 存进数据结构维护的操作可能会做多次，而整体二分只需要做一次。

所以这体现了离线的一种思想：对多个查询，只计算一次其公共部分。也就是多个询问相同部分一起算。

P9068 [Ynoi Easy Round 2022] 超人机械 TEST_95

P9068 [Ynoi Easy Round 2022] 超人机械 TEST_95。

这道题是求逆序对数，但是它定义的不同是指的权值不同，不是下标。所以我们可以记录每一个数第一次出现的位置，和最后一次出现的位置。

可以用差分思想，离线处理每一次修改的影响。

用五元组 $(x,y,0/1,t,k)$ 表示将 $x$ 的 $fst/ed$ 改成 $y$，$k$ 表示这是删除这个状态还是加入这个状态。

$(x,y,0,t,k)$ 的贡献是 $\displaystyle k \sum_{(x',y',1,t,k)}k[x' < x \wedge y' > y \wedge t'<t]$。

$(x,y,1,t,k)$ 的贡献是 $\displaystyle k \sum_{(x',y',0,t,k)}k[x' > x \wedge y' < y \wedge t'<t]$。

注意，只需要排一遍序，因为后面倒着枚举就行了，不然会被卡常。

莫队

很暴力吧，但是确实很有用。不过放在这里确实没什么好讲的，可能就带修莫队有一点维度的思想。

带修莫队相当于加上一个时间轴，就是现在已经修改到了多久了。至于排序...我们判断如果 $l$ 和 $r$ 都在一个块里面，比较时间。推荐块长 $n^{\frac{2}{3}}$。