集训之数据结构专题

A

题意简述

给定 $n$ 个数字，$q$ 个询问，每次询问一个区间 $(l, r)$，问多少个数对 $(p, q)$ 满足 $p < l, r < q, a_p = a_q$。

题目分析

考虑到问题区间可以通过单点移动求出来，即使用莫队算法，维护所给区间两边的数字个数，如果区间向一边收缩了一位，即有一边增加了一个数，答案就增加另一边相同数的数目，减少同理

B

题意简述

给定 $n$ 个数字，$q$ 个询问，每次询问给定一个数字 $d$，求 $d$ 长度区间覆盖的最大值的最小值。

题目分析

考虑单个点的贡献，建一个单调栈（严格单调递减）。假设从左往右扫，可以发现当前点往左可贡献的最大长度即是当前到单调栈第一个元素的距离。再从右往左扫一遍，合起来再减去重复的自身即可得到自身的高度可以贡献的最大长度区间。

考虑到对于大区间的答案同样适用于小区间，所以最后从大往小取 $\min$ 即可

还要注意所选区间为两边的情况（并不完全覆盖元素），可以将其处理为长度为 $n$ 的区间覆盖两边的端点。因为覆盖更多的点一定不会更优，且长度为 $n$ 可以覆盖小区间情况。

C

题意简述

求区间最大及最小值，询问是否满足给定公式 $2g(h_{max} - h_{min} + d) \ge v^2$

题目分析

区间最大及最小值可以用线段树，ST 表，分块维护。最后计算记得开 long long 即可。

D

题意简述

给定 $n$ 个物品，每个物品两个属性 $s$，$p$，再给定 $m$ 个物品，每个物品三个属性 $x$，$y$，$z$。求对于每个后一种物品，满足 $xs - yp \ge z$ 的前一种物品数量

题目分析

考虑到所需要满足公式不好维护，可以优雅暴力，使用 K-D Tree。预处理 $n$ 个物品，将方差较大的作为划分维度，将中位数作为划分依据，处理出每个结点的子树的最大及最小值。对于每个后一种物品在 K-D Tree 上搜索，如果 $xs_{min} - yp_{max} \ge z$，则代表整个子树都可以，返回子树大小即可；如果 $xs_{max} - yp_{min} < z$，则代表整个子树都不行，直接返回；否则统计当前结点贡献，再递归子树。

E

题意简述

给定一个环，环上有一根弦，边随时可能消失或出现。求给定两点的最短距离。

题目分析

主要是如何清晰地分类讨论。

首先用两个树状数组维护环上及弦上坏边的数量。这样即可快速求出环上两点或弦上两点可以联通的方式。

再写两个函数。第一个函数求环上两点通过只经过环边的最短距离。第二个函数求弦上两点通过只经过弦边的最短距离。

1. 环上两点

   1. 只经过环边，由第一个函数求得。
   2. 要经过弦边。枚举两点分别到达的环弦交点，再通过函数一和函数二组合求得。

2. 环上和弦上两点

   枚举弦上一点到达的环弦交点，再通过函数一和函数二组合求得。

3. 弦上两点

   1. 只经过弦边，由函数二求得。
   2. 要经过环边，枚举两点分别到达的环弦交点，再通过函数一和函数二组合求得。

F

题意简述

给定 $n$ 个数字，求 $\gcd(l, r)$ 的不同取值个数及其对应数目。

题目分析

考虑到区间 $\gcd$ 数目的个数很少（int 下最多 31 个），所以可以考虑暴力。假设以 $r$ 结尾的区间变化端点（指 $l$ 向左扩展区间 $gcd$ 发生变化的点，一个显然的性质是 $r$ 后移时，只会在前一个 $r$ 的变化端点上区间 $\gcd$ 可能发生变化，其他点不可能发生变化）存储在 map 中，对应 $value$ 值为个数。暴力枚举右端点，更新 map，更新 ans 即可。

G

题意简述

给定 $n$ 个数，$q$ 个询问，每次询问给定一个区间 $[l, r]$，求所给区间使 $a_i \times (n^{p_i} + \dfrac{1}{n})$ 最大的 $a_i$，其中 $p_i$ 为 $a_i$ 出现次数

题目分析

考虑到 $p_i$ 的权重比较大，猜测是否题意即是求区间众数。

考虑最极端情况。区间众数为 $1$，第二众数为 $n$，第一众数比第二众数出现次数只多 $1$。发现此时结论不成立。

考虑微扰一下。将 $1$ 换成 $2$；将 $n$ 换成 $n - 1$，将多的出现次数增大到 $2$，发现此时众数即是答案。（具体见我 PPT :)）

在区间众数为 $1$，第二众数为 $n$，且第一众数只比第二众数出现次数多 $1$ 的情况之外，区间众数即是答案。而所提到的特殊情况 $1$ 才是答案。若有多个众数，取最大的 $a_i$ 即可。

所以分块维护区间众数，但忽略 $1$。最后返回答案使单独考虑 $1$ 即可。

H

题意简述

给定长度为 $n$ 的序列 $a$，若存在 $1 \le i \le n$，使 $\forall1 \le j \le n$ 且 $j \ne i$，都有 $a_i \ne a_j$ 的 $a_i$ 为 $a$ 的合法数。

若对于任意区间的序列都存在一个合法数，则称这个序列为合法的。

给定一个序列，判断其是否合法。

题目分析

若存在一个数在一个区间只出现一次，则以这个数左边的点为左端点，右边的点为右端点的区间显然都是合法的，即只需要考虑左右端点都是两边的情况。

考虑分治，关键是如何快速找到这样一个分界点或者说如何找能保证复杂度正确。正确的方法是从两边找，找到了就递归下一层。

考虑其正确性。从两边找，找到就递归到下一层即类似于将较小的一段合并到大的一段的逆过程，而将小的合并到大的即是启发式合并的思想。这也是复杂度的保证。

I

题意简述

给定一棵树，每个点上有一个非负权值。有修改操作，询问操作。操作可以针对一条路径或者一个子树。询问是询问斐波那契数列的第点权项的和。

题目分析

首先想到树链剖分。考虑到点权很大，而且如果直接维护斐波那契数列中的数字不好更新。考虑维护斐波那契的递推矩阵，这样即可将区间加变成区间乘，并且具有结合性。所以树链剖分维护斐波那契矩阵 {{0, 1}, {1, 1}} 的 $k$ 次幂即可。

注意常数可能很大，可以考虑矩阵展开

J

题意简述

给定 $n$ 个路段，有 $m$ 个陷阱，陷阱只在指定时间内有效，给定 $q$ 个询问，求指定时间的指定区间有多少长度的路段没有被陷阱覆盖。

题目分析

考虑陷阱只在一段时间内有效，可以考虑线段树分治。可以将所求容斥一下，即求区间被陷阱覆盖的长度。每到达线段树分治点时即该点的陷阱覆盖操作。陷阱覆盖操作可以考虑用另一个线段树维护。

tag 表明区间是否被整体覆盖，标记永久化，如果当前区间 tag 没被标记，递归访问子区间查询即可；如果被标记即返回当前区间与所求区间的交集长度。最后所求区间长度减去区间陷阱覆盖长度即为所求。

K

题意简述

给定 $n \times n$ 的矩阵，每一点有一个权值。有三个操作，分别是单点增加，单行清空，单列清空。有一个询问，询问指定矩阵的权值和。

题目分析

观察到 $n < 1000$，很小，可以考虑二维线段树维护。

但不好维护单行清空和单列清空操作。注意到 $n$ 很小，第一次执行清空操作后，会至多清空 $n$ 个点，但后来每次有效清空的点只会是单点增加的。所以总共有效清空的次数即 $n \times n + m$，所以清空操作可以改为暴力枚举有效点并进行修改操作。所以即变成了二维线段树，维护单点增加，维护矩阵和的问题。

L

题意简述

$n$ 个鱼塘，$m$ 个鱼呈等差数列放入一个区间，注意鱼的种类可能相同，询问区间中一个池塘可以最多有多少同一种鱼。（一开始题面没写清，还以为要求和

题目分析

等差数列，单点最值，可以考虑李超线段树，只要将同种鱼的交集区间的方程合并，就是李超线段树的板子题。

先将方程转化为截距式便于合并。将同种鱼的序号存入同一个 $vector$ 当中，一起处理。每次处理同一种鱼时，记录每个方程的起始点和结尾点，遍历这些点进行相应的增加或减少即可合并，可以发现方程数量最多扩大到两倍。剩下就是李超线段树维护，查询每个点最值，ST 表求解区间最值。

M

题意简述

$n$ 个点，$m$ 条道路，但是只在一段时间存在，求问某个时刻两点的联通状态。

题目分析

考虑到道路只在一段时间存在，可以使用线段树分治。每到达分治结点，进行按秩合并即可（路径压缩不能回溯），还要注意将之前的状态压入栈中。回溯时弹栈还原状态即可。

N

题意简述

$n$ 个点构成一棵树，每个点上有一个权值，同时有一个集合 $S$，两种操作：一是从集合 $S$ 中增添数，二是询问 $u$ 和 $v$ 之间最短路径的点构成的权值集合 $S’$，询问 $\left| S \cap S’\right|$

题目分析

因为集合元素单点移动即可维护，所以操作一用一个 bool 数组维护，操作二用 cnt 数组在树上莫队维护即可。跑一下树的时间戳（括号序），得到树上每个点第一次出现和第二次出现的位置。然后查询时根据 $u$ 和 $v$ 的相对位置采用不同的方式查询即可。

具体是指（不妨令 $f$ 为第一次出现的位置，$g$ 为第二次出现的位置，且 $f_u < f_v$），若 $u$ 是 $v$ 的祖先，即 $f_u < f_v < g_u$（也可以暴力 LCA 判断），就查询 $f_u - f_v$ 之间的点即可；如果不是祖先，就查询 $g_u - f_v$ 之间的点即可，注意第二种情况漏了 $u$ 和 $v$ 之间的 LCA，统计答案时需要临时加上。这里的查询一个序列的点是指只在序列中出现一次的点，两次的点不计入答案。

O

题意简述

$n$ 个点构成一棵树，每个点一个权值，同时有一个类型。$m$ 个操作，操作一改变点的类型，操作二改变点的权值，操作三询问与 $x$ 同类型的点中和 $x$ 构成联通块的点中权值最小为多少。

题目分析

如果将同色点连边，改变点类型即是增删边，那就是典型的 LCT 问题了。但如果是直接暴力地增删边，则在菊花图中，每次增删边的数量会达到 $O(n)$ 级别。考虑优化，将不同类型的点分别建一个 LCT，每个点都在对应 LCT 内向父亲结点连边即可。这样最终构成的图形是除了原树的根节点，一棵树内所有点都是相同类型了。维护子树信息就多用某个东西维护虚边下的信息即可。这里的信息（最值）不具有可减性，需要用 multiset 维护。

转化后其实就是典型的 LCT 维护子树信息了，但此题注意查询时根节点的可能不是相同类型（除了作为原树的根结点的 1 以外是不能再向父亲连边，其他根结点都是和联通块内其他结点类型不同），所以查询要注意细节。具体是用 LCT 的 findroot 将原树（指 $x$ 的联通块）的根节点找到，并 splay 上去，如果根节点类型相同，直接查询根节点信息即可；如果类型不同则查询根节点的右儿子信息（刚好只去除了根节点）。

P

题意简述

若干操作，太长了 :(

题目分析

注意题目的两个限制。第一个限制：一个栈为空后就不会再有任何元素进入，所以查询空栈个数即是查询进行了多少一操作；第二个限制：每次查询元素排名时，临时栈没有任何一个元素，这代表每次查询时，元素必然都从临时栈转移到了原来的某个栈中！所以可以将操作一二看作一个整体，根据栈的性质两次进栈出栈刚好没有改变原来的次序！

将一二看作一个整体后，就是将一个栈的元素在保持原来的次序不变下转移到另一个栈中，变成了一个典型的带权并查集。在原来的并查集基础长维护到根节点的距离，每次改变父亲时，更新信息即可。注意最终查询的是到栈顶的信息，所以再维护一下栈的大小，和到根节点的距离相减一下即是到栈顶的距离。

Q

题意简述

给定 $n$ 个点的树，每个点有一个权值。再给定一个点集合，求另一个点集合，要求是：使这些点联通的最少点集合。输出这个点集的权值和。

题目分析

考虑 dfs 序性质。首先考虑给定一个点集，如何快速找到题目所求集合或者说不找到这个集合，只求出这个答案即可。将点权转化为到父节点的边权，按照 dfs 序将点集排序构成一个环，发现相邻两点的距离和除以 2 即是使他们联通的最小边权和。但是因为我们是将点权转化为了边权，遗漏了 LCA 的点权，所以还要加上 LCA 的点权。

而一堆点的 LCA 其实就是 dfs 序最小的点和最大的点的 LCA，所以再写倍增，ST，树剖等维护一下 LCA 即可。

再发现查询的点集可以每次增减一个点来维护答案，所以写个莫队维护点集即可。

R

题意简述

$n$ 个点，每个点一个权值，三个操作：操作一区间取 $\log$，操作二区间加，操作三查询区间和。

题目分析

如果没有操作一就是典型的线段树问题。考虑操作一，可以发现是和 $\sqrt{}$ 操作一样区间差值（或者对于 $\log$ 操作来说，每个值）衰减地很快。试验发现，INT_MAX 5 次 $\log$ 操作即可化为 0，所以如果暴力更新叶子结点，则每个叶子最多更新 5 次。这在可接受范围内。

如果考虑到操作二，区间加，那么为了保证复杂度，区间一更新条件需要变为区间内值不同，否则可视为一个区间减操作。还有一个像区间 $\sqrt{}$ 一样优化，即如果最大值和最小值在 $\log$ 后差值不变（可证明两者最多差 1），也可以转化为区间减操作，但正如题解所说优化不大。

S

题意简述

太长了，就是吉司机树操作大杂烩 :(

题目分析

操作一到三都是吉司机线段树典型题。

对于操作四：
对于操作一的修改，很简单，就是一个区间加，维护一下区间个数，打 tag 即可。而对于操作二的修改，只会对最大值有影响，而吉司机树刚好维护了最大值个数，也打 tag 即可，但注意下传时传给哪个儿子。

对于操作五：
维护一下最大值和其他值的历史下传最大 tag 即可。

对于操作六：
维护一下最大值和其他值的历史下传最小 tag 即可。注意最大值的历史最小 tag 不可省略，如果想省略，用各种特判乱搞可能 WA 惨 :(。

剩下的就是注意细节。如怎么判断最大值 tag 下传到哪个区间（用两个子区间的最大值判断，因为此时父区间的最大值已经变了）。又如什么时候要更新各种 tag。又如下传 tag 时，更新的先后顺序。又如最小值要用哪个 tag 更新。又如最小值和最大值相同时的特判。

然后微笑着 debug :)。

T

题意简述

$n$ 个点，每个点有一个权值。$m$ 个询问，每次询问给定参数 $l$, $r$, $x$，若只保留 $l$ 到 $r$ 的点，问编号为 $x$ 的联通块内有多少个点小于等于 $x$ 的权值。（吐槽一下题面写的是小于，但要求输出写的和实际是小于等于）

题目分析

很妙的一道题。每次询问与树的形态无关，可以考虑点分树来“暴力”。

考虑如何对每个询问求解。我们可以将每个询问安放在点分树上与 $x$ 所联通的层数最小结点（不妨令为 $y$），其余联通的子节点必然在其子树下。
证明：若还有一个联通结点在子树外（不妨令为 $z$，有两种情况：一是是该节点 $y$ 的祖先，另一种情况不是。第一种情况与 $x$ 相悖，不成立。第二种情况，由点分树的性质，$y$ 和 $z$ 的 LCA 必然是 $y$ 到 $z$ 路径经过的一点，与 $x$ 相悖，不成立。

至于如何找到这一结点，可以建立点分树后，不断从 $x$ 向上跳，最后一个满足约束的即是层数最小的结点。

考虑约束函数如何写：可以转化为求两点之间路径经过的最小点 $minx$ 和最大点 $maxx$。这个可以将点权转边权，倍增维护。判断 $minx \ge l \land maxx \le r$ 即可。

现在询问已经安置了，那么如何具体求解呢？

考虑点分树的“暴力”，对每个点都暴力统计子树信息，同样是统计该点到子树根节点所经过的最小点 $minx$ 和最大点 $maxx$，但还有该点的权值。发现如果一个点（不妨令为 $y$）对一个询问有贡献，则需满足 $minx \ge l \land maxx \le r \land val(y) \le val(x)$。即三个维度的大小比较，发现如果我们对每个询问都遍历一下子树都统计答案，那么复杂度是难以接受的，所以我们想到将同一个点的询问合在一起来统计答案，那么其实就是一个三位偏序问题，但需要在次基础上改改，针对性地修改，针对性地统计答案。这样，每个点至多在 $\log(n)$ 个三位偏序里跑，也就是说跑三位偏序的结点数总共有 $n\log(n) + m$ 个，而这是可以接受的。

至于三维偏序的维护见 W 题。

U

题意简述

各种操作杂烩 :(

题目分析

首先一定要注意到的是将某个数提到某个数之前可以用翻转操作实现。但问题是区间翻转后序号信息会乱。如果将序号信息作为数组下标，在 fhq 树中又如何进行区间翻转操作呢（fhq 区间翻转需要指定序号元素在序列中的位置）。

因为一般情况下，fhq 树层数不超过 $\log(n)$ 层，所以可以考虑暴力跳父亲来获取在原序列排名信息，可区间 tag 又怎么维护呢？考虑用栈存起来，再自顶而下地 donwTag 即可。在向下 downTag 的过程中顺便统计 rank 信息。

所以我们就可以得到一个 $\log(n)$ 获取一个数的在原数列的排名信息的做法。解决了这个问题，剩下就是平衡树板子了。

V

题意简述

真·并查集板子题

题目分析

敲并查集板子即可…最后答案就是不断乘以 2 加上当前查询答案模以指定数的过程。

还是多写写吧…

可以考虑路径压缩优化，路径压缩就是将自己的父亲指向祖先（当前联通块的代表元素）。

也可以考虑按秩合并，将小的合并到大的。

查询是否联通即是看代表元素是否相同。

W

题意简述

维护三位偏序（但感觉题意还是有歧义的

题目分析

第一维排序即可，第二维和第三维考虑 CDQ 分治和树状数组。

具体是递归统计两点都在一边的答案，再统计两点在两边的答案。第二维的有序可以考虑归并，这样也可以保证复杂度。

递归两边后，两边都是有序的，对于右边的每个元素，统计一下左边的元素有多少个满足限制。具体是：维护两个指针（不妨令为 $i$ 和 $j$），第一个指向左边的元素，第二指向右边的求解元素，$j$ 向后移动时，$i$ 移动到最后一个第二维小于等于 $j$ 元素的位置，移动过程中向树状数组加入第三维信息，最后统计当前 $i$ 的答案，继续向后移动 $i$ 即可。最后按第二维归并保证复杂度。

这样 CDQ 分治，归并，树状数组可以保证复杂度为 $n\log^2(n)$。

注意要去重并统计个数，不去重会导致相同元素地位不对等。再注意一下两个排序函数的写法，一定要保证只有左边的元素才能是右边元素的候选答案。还要注意树状数组要回溯清空来保证复杂度。

X

题意简述

$n$ 个点，每个点权值，将连续的相同权值视为一段。操作可以改变点权值，求某个时刻的段数。

题目分析

如果对每个权值都用一个动态开点线段树，发现这个信息是很好合并的，只要再多维护最前和最后是否为该线段树维护的权值，线段树向上 up 时，如果左区间的最后是且右区间的最前是，那么合并时颜色段数减一。

而改变一个整体颜色的过程其实就是线段树合并的过程。

合并两棵线段树时，做类似的操作即可。

Y

题意简述

给定 $n$ 个物品，每个物品三个属性，再给定 $m$ 个询问，每个询问给定两个参数，要求所选物品在满足两个属性限制下，求第三个属性最小值最大为多少。

题目分析

最小值最大，可以考虑二分。二分后就限制了所选物品，现在问题变为了如何判断一些物品能满足两个限制。

注意体积可以拆分，所以单位体积价值越低的物品越优，根据贪心，我们优先选单位体积价值更低的物品，并且刚好选 $C$ 体积元素（如果选不到则代表不成立），判断此时价值总和是否超过 $V$ 即可。

但是现在是有 $m$ 个询问，且已经有了一个 $\log$ 的二分复杂度，如何能快速判断是否合法呢？

因为单位体积价值更低的物品更优，且信息很容易用线段树维护，所以我们可以考虑主席树，将单位体积价值作为主席树序列下标，主席树维护区间体积和区间价值，询问时在主席树上二分到一个体积刚好为 $C$ 的位置，返回此时的价值，跟 $V$ 比较即可。

Z

题意简述

线段树套平衡树板子。

题目分析

因为操作即涉及到了区间，又涉及到了如查询 rank, value, pre, nxt 等平衡树经典维护的信息，所以写线段树套平衡树即可。

操作一查询指定值的排名，递归线段树区间，对区间平衡树统计比其小的有多少，最后加起来再加 1 即可。

操作二查询指定排名的值，直接求解会比较困难，可以考虑二分转化为操作一。注意这里二分有一个细节，一定是二分出最后一个小于等于的数，不能是二分出第一个大于等于的数，主要是要考虑多个相同的数的影响与排名的定义。

操作三修改权值，递归线段树，修改对应平衡树即可。

操作四查询前驱，递归线段树，查询每个平衡树的前驱取 $\min$ 即可。

操作五查询后驱，递归线段树，查询每个平衡树的后驱取 $\max$ 即可。