2021 Noi.ac 省选专题营 Day 1 笔记

时间：20210811 讲师：冯哲 专题：分治、分块、构造

1.1 分治：

1.1.1 定义：将原问题 $P$ 分为若干个子问题 $P1,\cdots,Pk$（一般来说原问题 $P$ 和现问题 $P_i$ 具有相同或者类似的问题模式）；然后解决 $P_i$ 之间存在的相互之间依赖关系，分别处理每个子问题；最后用每个子问题的解解决原问题。

1.1.2 分类：

1. 直接分治，如归并排序、卷积等，直接用子问题的解得出原问题的解。
2. CDQ 分治：须处理两个子问题之间的贡献，再往下递归求出每个叶子结点权值的分治。
3. 计数分治：常用于统计满足每个条件的区间个数（将其转化为计算跨过中线的区间个数）
4. 线段树分治：用于解决“补集”类的问题。

1.2 主定理：

主定理用于计算如下递推式的复杂度：

1. 当 $f(n)=n^{\log_b{a}-\epsilon}$ 时：$T(n)=O(n^{\log_{b}a})$。
2. 当 $f(n)=n^{\log_ba}$ 时：$T(n)=O(n^{\log_ba}\cdot\log{n})$。
3. 当 $f(n)=n^{\log_b{a}+\epsilon}$ 时：$T(n)=O(f(n))$。

对于二分式的分治，$\log_2{2}=1$，于是就直接添上一个 $\log$ 即可。

1.3 分治例题精选：

1.3.1 分治乘法

对应于第一类的分治；注意：当分治中的 $a>2$ 时可能会严重影响复杂度，需要对着 $a$ 大力卡常。

1.3.2 [WF2011] Machine Works

一个公司获得了一个厂房 $n\in(0,10^5)$ 天的使用权和一笔启动资金 $C(10^9)$，准备在 $n$ 天里租借机器生产来获得收益

可以租借的机器有 $M(10^5)$ 个，每个机器有四个值，$D,P,R,G (D \le n, P,R,G \le 10^9)$

表明你可以再第$D$ 天花费 $P$ 费用（首先手里必须有那么多钱）租借这个机器，从 $D+1$ 天开始该机器每天产生$G$ 的收益，在你不需要机器时可以卖掉这个机器，一次获得 $R$ 的钱。同一时刻只能拥有一台机器，问最大收益。

这是第二类的分治。首先我们可以得到一个显然的 dp 方程：

这个方程是一个 $j$ 的一次函数，那么优化转移就只需要维护一个动态的半平面交；考虑李超树 / cdq + 半平面交就可以维护。

考虑更简洁的实现方法：我们将这个方程按照常规套路进行转化，会转化为一个上凸壳的问题，但是需要支持动态加点；可以使用 splay 维护，也可以直接 cdq（结合归并也可以做到一个 $\log$）。

1.3.3 Permutation

给定一个排列，问有多少个连续子段满足：排序后是一个连续序列。

第三类分治。我们直接分治下去，统计有多少个跨过中线的满足条件的子段；一个子段满足要求的条件等价为 $\max-\min=r-l$；我们分类讨论 $\max$ 和 $\min$ 在中线的那一边，然后尺取法即可做到 $O(n\log{n})$。

我记得 2020 有一次 $\mathrm{lxl}$ 的一场模拟赛中有一个类似的题目，详见这个：https://www.cnblogs.com/Linshey/p/14165532.html。

1.3.4 百度地图的实时路况

给定一张有向图 $(n\le 300)$，设 $W(u,v,w)$ 为不经过 $w$ 点的 $u$ 到 $v$ 的最短路，求：

$$\sum_{u,v,w\in[1,n],u\not=v,v\not=w,w\not=u}W(u,v,w)$$

这是一个第四类的分治。floyd 的性质是，我们只要不加入这个点，那么最短路就不经过这个点。于是 $W_w$ 就是把除了 $w$ 之外所有点都加入 floyd 的结果。维护这个东西，我们直接线段树分治一样地分治下去，就可以维护出补集的信息。时间复杂度 $O(n^3\log{n})$。

1.3.5 [Codeforces]LWDB

给出一棵带边权的树，有两个操作:

1. 把距离 $x$ 这个点不超过 $d$ 的点全部都染成颜色 $c$ ,初始所有点颜色为 $0$.
2. 询问点x 的颜色。N ,Q ≤100000.

点分治模板题，转化为最大时间，直接维护即可。

1.3.6 [Zjoi2016]旅行者

$n$ 条东西向道路和 $m$ 南北向道路交叉形成了 $n\times m$ 个格点。每个点到周围点有一个代价 $c_{i ,j},r_{i ,j}$ [道路是双向的],$Q$ 组询问，每次询问从 $(sx_i ,sy_i)$ 走到 $(ex_i ,ey_i)$ 的最短路。 $n\times m ≤2\times 10^4$，$q ≤10^5$。

我们直接将当前矩形的长边，按照中线分成两半。我们对这条中线上的每个点都进行一次单源最短路；然后对于每个当前矩形中的询问，我们都在边界上枚举一个点，找到它们经过中线的最短路；然后递归下去即可。

正确性：对于在中线两边的询问，它们一定跨过中线；对于在同侧的点，在当前矩形内的答案可以完全递归下去，中线的情形已经枚举了出界的情况。

时间复杂度：对于每次递归，中线长度 $=\min(n,m)\le \sqrt{nm}$，递归的复杂度是 $O({(nm)}^{1.5}\log{nm}$ 的。而每个询问只会被遍历 $\log$ 次，询问的复杂度是 $O(q\log{nm})$。

2.1 分块

2.1.1 分块：将序列分成 $S$ 块，每块整体处理，用以平衡复杂度。

2.1.2 重要性质：对于每个块的左端点，都遍历一遍右端点，这个东西的复杂度是 $\frac {n^2}S$ 的；块数的平方是 $\left(\frac nS\right)^2$ 的。一个经典应用是：利用这个重要性质，我们可以得到一个 $O(\sqrt n)$ 修改 $O(1)$ 询问的维护可减性信息的分块。

2.1.3 莫队：即动态维护一个上述的分块；当然，维护的信息也就可以更多样，甚至可以维护一个对应于这个区间的数据结构。

2.1.4 值域分块：常见的是对于值 $\le\sqrt{n}$ 的询问和大于 $\sqrt{n}$ 的东西分别想做法；当然还有一种是，对于 $\sum a_i = O(n)$ 时，$\sum\min(a_i,a_j)=O(n^{1.5})$。

2.1.5 与线段树对比：无需可以快速下传的 $\mathrm{tag}$ 和可以快速合并的性质。

2.1.6 树上莫队：在欧拉序上莫队即可。

2.2 分块例题精选：

2.2.1 Isolation

给出一个长度为 $n$ 的数组 $a\ (1 ≤ai ≤n)$。同时在给出一个 $k≤n$，求把这个序列分成若干块，使得对于每个区间，只出现一次的数字个数不超过 $k$ 个。$N ≤100000$。

从左往右考虑，对于每个数，都只要保留最后两个这个数就行，在这个区间内它贡献为 $1$。我们每次 $i+1$ 相当于一次区间抬升和一次区间下降，问高度在 $k$ 以内的数的和。

直接用分块维护，对于每个块，维护一个值域的桶和一个偏移标记即可。优化 dp 时，直接当作数据结构题做，思路打开来，分块啥的都用起来。

2.2.2 [Shenyang Regional 2021]Descent of Dragons

给定一个长度为 $N$ 的序列 $A$，初始全为 $0$，要求支持以下两种操作:（$N ,Q ≤100000$ 带修区间众数）

1. 把所有 $[Li ,Ri]$ 中等于 $x_i$ 的数都变为 $x_i + 1$。
2. 询问 $[Li ,Ri]$ 中的最大值。

我们发现数的大小关系不会发生改变！我们预处理出每个数在块中的排名，并在每个块中维护一个值域的桶；重构时我们从大到小扫描所有非 $0$ 位置的桶（这个直接在修改时加入队列），从大到小分配给块内的数，即可。

2.2.3 带修区间众数

直接三维莫队 + 平衡树，$n^{\frac 53}\log{n}$。

我们发现询问的复杂度极其小，可以考虑和修改平衡一下；直接值域分块，记录出现次数在块内的数右多少个即可。

$O(n^{\frac 53}+q\sqrt{n})$。