数据结构杂题选讲

讲师：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

题意：

在平面直角坐标系中维护两个操作：
$i$ 。
$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$ ，保证存在至少一个划分方案。

题解：

$1$ $-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$ 次操作：
$k,v$ $a_k\leftarrow v$ 。
$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 即可。