数据结构杂题选讲.md

数据结构杂题选讲

讲师：PinkRabbit 时间：20210630 地点：福建师大附中

Example.1 Siano

题意：

有 $n$ 亩土地，一开始都是空的，一个农夫要在上面种草。

其中，第 $i$ 亩土地的草每天会长高 $a_i$ 厘米。

农夫一共会进行 $q$ 次收割，其中第 $i$ 次收割在第 $d_i$ 天，并把所有高度大于等于 $b_i$ 的部分全部割去。

输出每次收割得到的草的高度总和。

数据范围：$n,q≤5×10^5$，$1≤a_i≤10^6$，$1≤d_i,b_i≤10^12$。且 $d_i<d_{i+1}$，任意时刻不存在一亩草高度超过 $10^12$。

题解：

倘若每次收割不互相影响呢？我直接按照 $a$ 排序，二分出高度，然后线段树维护即可。

这时我们发现，即使有收割，它也是单调的，我们依然可以二分。

Example.2 动态图

题意：

维护一张无向图，支持加边、删边、询问连通性。

允许离线，数据范围：$n,q≤10^5$。

题解：

线段树分治模板题，不多解释。下略例题 3、5，因为类似。

Example.4 直径

题意：

给定一棵树，$q$ 次询问，给定 $a,b,c,d$，求 $x∈[a,b]$ 且 $y∈[c,d]$ 时 $dis(x,y)$ 的最大值。

数据范围：$n,q≤10^5$。

题解：

考虑单点 $y$ 到点集 $[a,b]$ 的最远距离，显然把 $[a,b]$ 放大为它的虚树答案不变；众所周知：

一个点到树的最远距离一定在直径端点处取得。

再考虑把 $y$ 扩大为点集 $[c,d]$，同理，到 $[a,b]$ 端点的最大距离，也是再 $[c,d]$ 的直径端点上取得。

因此，只要找到四个端点，两两组合就能算出答案。

如何计算区间 $[a,b]$ 的最远点对呢？我们可以增量构造，每次在原有直径的基础上进行判断，加上回滚莫队即可。

但是着并不够巧妙。由于有合并的性质，我们直接拿线段树维护这个东西，PushUp 时直接用这个性质进行合并。

Example.6 Segment

题意：

在平面直角坐标系中维护两个操作：

1.加入一条线段，编号为 $i$。

2.询问与竖线 $x=k$ 相交的线段中，交点最高的线段的编号。

强制在线，数据范围：$1≤横坐标≤40000$，$q≤10^5$，$1≤纵坐标≤10^9$。

题解：

如果用李超树的话，复杂度 $O(n\log^2n)$，下面介绍一个牛逼方法：D-S 序列。

考虑加入 $n$ 个 $s$ 段的分段函数，那么它的上包络线段数小于等于 $\lambda_{s+2}(n)$，并且有：

$\lambda_1(n)$	$\lambda_2(n)$	$\lambda_3(n)$	$\lambda_4(n)$
$n$	$2n-1$	$2n\alpha(n)+O(n)$	$O(n2^{\alpha(n)})$

可以看到这个级别是很小的。我们暴力维护顺序维护每一段，显然可以 $O(\lambda_{s+2}(n)+\lambda_{s+2}(m))$ 合并两个包络线。

如果是一并输入的话，我可以分治一下，然后大力合并。

如果是动态输入的话，可以使用二进制分组法，这么做是两个 $\log$ 的。利用分散层叠可以优化掉一个。

Example.7 楼房重建

题意略。这里将一个重要的衍生方法。

PinkRabbit 法：

正常的楼房重建，每个区间维护的是这个区间的答案，然后查询的时候向下二分。这么做的话需要可减性。

但是其实可以维护每个右区间对本区间答案的贡献，这样子二分下去做就不需要可减性。

Example.8 Election

题意：

Alice 和 Bob 要竞选总统。

有 $n$ 个选民，编号为 $1∼n$，他们中有的人支持 Alice，有的人支持 Bob，还有的人保持中立。

现在你需要把选民分成若干区间，每个区间的长度在 $[l,r]$ 中，如果一个区间中支持 Alice 的人比支持 Bob 的人多，那么 Alice 得一票，如果一个区间中支持 Bob 的人比支持 Alice 的人多，那么 Bob 得一票，如果一个区间中支持 Alice 的人和支持 Bob 的人一样多，那么两人均不得票。

Alice 想要赢得选举，她请你合理地划分区间，使得她获得的票数减去 Bob 获得的票数尽可能大。

数据范围：$1≤l≤r≤n≤10^6$，保证存在至少一个划分方案。

题解：

令支持 Alice 为 $1$，Bob 为 $-1$，记录前缀和为 $s$，则： $$ f[n]=\max_{i=0}^{n-1}f[i]+[s_n-s_i>0]-[s_n-s_i<0] $$ 维护中，对于每个 $s$ 建一个单调队列，每次都扔进去，并且记一下；弹出的时候，一次必然只会弹出一个；然后用线段树维护一下单调队列队首元素的区间最值，即可。

Example.9 文明城市

题意：

给定一棵树，点权有正有负。

执行 $q$ 次修改点权的操作，每次操作后询问连通块点权之和的最大值。

数据范围：$n,q≤10^5$。

题解：

DDP 写矩阵的最好方法是：假设是静态、链上的问题，于是有方程： $$ \begin{bmatrix}0 & a_i & a_i \ -\infty & a_i & a_i \ -\infty & -\infty & 0\end{bmatrix}\times\begin{bmatrix}\max \ \operatorname{suf} \ 0 \end{bmatrix} = \begin{bmatrix}\max' \ \operatorname{suf'} \ 0 \end{bmatrix} $$ 然后因为链上和树上的方程实质上是等价的，于是就列完了。所以考虑链上问题是解决 DDP 的一个好方法。

每次修改中，先单点修改，然后再单点修改此轻链链顶的父亲，依次类推……

Example.10 线段树

题意：

给定一个长为 $n$ 的数组 $a$。

有 $m$ 个操作，编号为 $1\sim m$，每个操作形如把区间 $[l,r]$ 内的数置为这个区间的最大值。有 $q$ 次操作：

1.给定 $k,v$，修改 $a_k\leftarrow v$。

2.给定 $x,y,k$，询问如果依次执行编号为 $x\sim y$ 的操作，$a_k$ 将会是多少。

数据范围：$n,m,q≤10^5$。

题解：

显然每个点对应一个区间的最值，而具体 $a_i$ 是什么数其实很好维护，难的是怎么找到对应的区间。

这时有一个重要的事情：考虑从 $y$ 操作反推到 $x$ 操作，这样就只需要维护单个 $[l,r]$ 就行了；而顺推需要维护所有的点的 $[l,r]$。

并且我们发现 $l$ 和 $r$ 是相互独立的，因此我们直接分别倍增维护。记 $f_{x,j}$ 为在 $x$ 操作处向左有效的 $2^j$ 步，$l$ 会从 $l_x$ 移动到哪里。注意，一定是要找有效的步骤，即 $now\in[l,r]$ 的步骤，不然就不能保证 $l=l_x$。

Example.11 树上的路径

题意：

给定一棵 $n$ 个结点的树，每条边有正整数权值。

求出 $dis(a,b)$（$1≤a<b≤n$）从小到大排序后的前 $m$ 个值。

数据范围：$n≤5×10^4$，$m≤3×10^5$。

题解：

直接超级钢琴套点分树即可辣！

Example.12 等差数列

题意：

给定一个长度为 $n$ 的数列 $a_1∼a_n$。

有 $q$ 次操作，每次要么修改数列某一项，要么给出 $l,r,k$，询问区间 $a_l∼a_r$ 中的数从小到大排序后能否形成公差为 $k$ 的等差数列。

强制在线。数据范围：$n,q≤3×10^5$，$0≤a_i,k≤10^9$。

题解：

只要判断三个条件，差分的 $gcd=0$、极差为 $(r-l)\cdot k$、没有重复的数（$k=0$ 除外）。

Example.13 Good Subsegments

题意：

给定一个长度为 $n$ 的排列。

有 $q$ 次询问，每次给定一个区间，求这个区间的所有是连续段的子区间个数。

连续段的定义是排序后形成公差为 $1$ 的等差数列。

数据范围：$n,q≤1.2×10^5$。

题解：

考虑 $q=1,l=1,r=n$ 时怎么做？直接从左往右扫，结合两个单调栈来维护 $\max-\min+l-r$，并且查询最小值个数。

那么结合上区间，直接在扫描到 $r$ 时查询一下 $[l,r]$ 的历史最小值和历史最小值个数，这时吉老师线段树的问题。

Example.14 Puzzled Elena

题意：

给定一棵 $n$ 个结点的有根树，每个点有正整数权值 $a_i$。

对于每个点，输出它的子树中有多少个点的权值与它的权值互质。

数据范围：$n≤10^5$，$a_i≤10^5$。

题解：

先反演一波—— $$ \sum [\gcd(a_i,m)=1]=\sum\sum_{k|m,k|a_i}\mu(k)=\sum_{k|m}\mu(k)\cdot s(k) $$ 注意到 $\mu$ 的性质，只需要处理 $2^{\omega(m)}$ 种 $k$ 即可；考虑如何维护 $s$，既然不能线段树合并啥的，那就只能考虑做差法，进入子树的时候算一次，出子树的时候算一次；加入一个数的复杂度是 $\sigma_0(m)\le 2\sqrt{m}$ 的。

Example.15 Odwiedziny

题意：

给定一棵 $n$ 个结点的树，每个点有点权。

有 $q$ 次询问，每次给定 $x,y,k$，表示从 $x$ 出发每次朝 $y$ 方向跳 $k$ 条边的距离，如果当前点和 $y$ 距离不超过 $k$ 就直接一步跳到 $y$，请求出经过的所有点的点权和。

数据范围：$n,q≤10^5$。

题解：

分治一下，$k\ge \sqrt n$ 直接暴力跳；$k\le\sqrt n$ 的预处理一下。

考虑怎么在 $O(n^{1.5})$ 时间内完成预处理——这里有一个小 Trick：到每个点，用栈把它到根的链记录下来，然后对每个 $k\le \sqrt n$ 都分别计算；查询时，我先算出 LCA，并在 $O(\sqrt n)$ 的时间内从 LCA 往上跳，跳到一个深度与 $u$ 点关于 $k$ 同余的点，算出点权和；在 $v$ 上方 $\sqrt n$ 个点中也暴力找到与前边同于的点，同理再算出第二条链上的点权和。

Example.16 Bear and Chemistry

题意：

给定一张有 $n$ 个结点 $m$ 条边的无向图。

有 $q$ 次询问，每次给定一些边和一些点，询问在原图基础上加入这些边后，这些点是否在同一个边双连通分量中。

数据范围：$n,m≤3×10^5$，询问时添加的边数和询问的结点数之和分别不超过 $3×10^5$。

题解：

当然是先缩点，建出由新边端点和询问点组成的虚树，然后将这颗虚树拿去 Tarjan 即可。

Example.17