数据结构听课笔记

· · 算法·理论

讲课人：jiangly，机构：代码源，侵权致歉。

只写了自己会的，有些还没研究懂，以后应该会再更新吧。

QOJ9918

一颗 n 个点的树，每个点上可以安装护盾。

可以激活，伤害会减半，不能在连续两次攻击内激活两次。

1. $x$ 到 $y$ 上受到了伤害为 $z$ 的攻击。 2. 假设 $x$ 上当前有一个没被摧毁的护盾，初始生命是 $h$，安装时间未知，问这个护盾最多承受了几次攻击。 $n\le 5\times 10^5,q\le 3\times 10^5

考虑动态规划，假设我们已经确定了一个护盾的操作序列，则设计 f_{i,0/1} 表示第 i 个操作没选或选，前 i 个操作挺过去最少需要多少初始生命。

考虑矩阵维护。把式子写成 2\times 2 矩阵，可以更好的快速维护。

原题变为链加入矩阵，单点求答案。

求答案时在线段树上二分是简单的，这部分复杂度 O(\log n)。

如果整体二分则复杂度爆炸，考虑换维。

考虑线段树合并，修改和查询的时候直接挂上去，问题因为自带时间维度所以离线没有影响。

时间复杂度 O((n+q)\log n)。

CF1852F

有 q 个事件发生在数轴上：

  1. 在时刻 t 坐标 x 出现了 c 个红点，红点可以向左向右走路也可以不动。
  2. 在时刻 t 坐标 x 出现了 c 个蓝点，蓝点出现的时候如果这个位置没有红点会消失，否则会匹配上一个红点并同时消失。

时间按照 x 非严格递增顺序给出，问你在每个事件作为初始条件后最多能匹配几对点。

--- 考虑建立 $t-x$ 坐标系，一个红点可以匹配他上方一个 $90°$ 的夹角，蓝点是被匹配的。 匹配问题是二分图上的，我们可以从二分图的各种数值里选一个替代，根据直觉我们要选择最大独立集。 转化为，一个折线可以 $\pm 1$，上方全部点亮红点，下方全部点亮蓝点。 设计 $f_{x,y}$ 表示折线当前走到了 $(x,y)$。一种转移是走点，另一种选择是按照目前位置的红蓝点更新 $f_{x}$。如果考虑维护 $f_x$ 的差分，会更加简单。只需要考虑差分的移动。其形成了若干连续段，是可以快速用数据结构删除的，而总段数只会减少，所以时间复杂度是均摊的。 # CF1942H 一颗 $n$ 个点的树，根是 $1$，每个点有权值 $a_i$，初始为 $0$。 有 $q$ 个操作： 1. 对点 $x$ 进行 $v$ 次生长：选择一个在 $x$ 子树内的点或 $x$ 的父亲 $y$，将 $a_y$ 增加 $1$。 2. 对点 $x$ 进行 $v$ 次收获：选择一个在 $x$ 子树内的点 $y$，将 $a_y$ 减少 $1$，减少完不能是负数。 给你数组 $b_i$。对操作序列每个前缀问是否能够重排操作顺序且选择最优策略使得执行完这些操作后 $a_i \ge b_i$。 --- 收获操作是子树，所以生长操作使用父亲只是为了匹配 $b_i$。 最终的贡献应该是分为 $a,c$ 两种贡献，$a$ 是生长 $c$ 是收获，而这个需要满足 $a-c-b\ge 0$。 于是考虑二分图匹配。从 $b$ 点连出到 $a$ 的边有儿子和祖先，从 $c$ 点连出到 $a$ 的边有祖先和子树。问是否可以达到最大匹配。 根据 Hall 定理我们有 $\displaystyle \sum_{i\in N(S)} a_i \ge \sum_{i\in S}(b_i+c_i)$。那么我们尝试找到 $\displaystyle \sum_{i\in N(S)}a_i - \sum_{i\in S}(b_i+c_i)$ 的最小值。 设计 $f_{u,0/1}$ 表示 $u$ 子树内被匹配的 $a$ 是单点还是子树时的答案。 转移时考虑自己是否要选择 $b,c$。 1. $b,c$ 都不选。$\displaystyle f_{u,0}=\sum_{v\in s(u)}\min(f_{v,0},0)$。 2. 选 $b$ 不选 $c$。$\displaystyle f_{u,0}=\sum_{v\in s(u)}f_{v,0}+a_u-b_u$。 3. 选 $b$ 且选 $c$。$\displaystyle f_{u,0}=f_{u,1}=\sum_{v\in s(u)} f_{v,1}+a_u-b_u-c_u$。 选 $c$ 不选 $b$ 不优。多组询问只需要动态 dp 即可。 # CF1876G Clubstep 是 Chaneka 喜爱的电子游戏（几何冲刺）中最难的关之一。Clubstep 中包含 $n$ 关，从 $1$ 到 $n$ 编号。Chaneka 已经对这个游戏进行了大量练习，所以目前她对其中的第 $i$ 关的熟悉度是 $a_i$。 之后，Chaneka 可以在 Clubstep 上进行若干次（可以是 0 次）尝试。在每一次尝试中她会在 $n$ 关中的某一关挂掉。某次尝试在第 $p$ 关挂掉意味着她通过了 $[1,p-1]$ 中的每一关，且没有进入 $[p+1,n]$ 中的任何一关。一次挂在第 $p$ 关的尝试用时 $p$ 秒。 我们知道 Chaneka 在自己挂掉的那一关上会比其他任何一关进步更多。我们也知道在一次尝试中 Chaneka 在自己没有进入的关卡无法取得进步。所以一次挂在第 $p$ 关的尝试的影响如下： - Chaneka 对第 $p$ 关的熟悉度增加 $2$。 - Chaneka 对 $[1,p-1]$ 中的每一关的熟悉度增加 $1$。 现在有 $q$ 个询问，第 $j$ 个询问给定三个正整数 $l_j,r_j,x_j$。你需要求出 Chaneka 通过若干次尝试后对 $[l_i,r_i]$ 中的每一关熟悉度都不小于 $x_j$ 的最小用时（以秒为单位）。注意每次询问都是独立的，所以 Chaneka 在某次询问中的尝试不会影响其他任何一次询问的熟悉度。 --- 考虑如何求解子问题。 从 $r$ 扫到 $l$，贪心的去操作，求解 $f(l,r,x)=f(l,r-1,x-\max(\lceil\dfrac{x-a_i}{2}\rceil,0))+\max(\lceil\dfrac{x-a_i}{2}\rceil,0)$。 考虑如何优化，使用楼叉楼科技：插入标记回收算法。 1. 在 $r$ 处加入集合 $S$。 2. $S\leftarrow f(S)$。 3. 在 $l$ 处回收答案。 现在问题在于如何快速进行第二部操作。 经典的，将 $S$ 内部的势能设计成 $\displaystyle\sum_{i=1}^{|S|-1} \log(S_{i+1}-S_i)$。并且假设我们已经将相同的值缩在了一起，用平衡树维护。 于是可以暴力变换需要变换的点值，每次变换使用 $k$ 的代价去消耗 $k$ 的势能，而插入点对会增加 $\log V$ 的势能，时间复杂度 $O((n+q)\log V)$。 # CF1515H $n$ 个数 $a_1,a_2,a_3,...,a_n$，$q$ 次操作： 1. 把 $l\le a_i \le r$ 的 $a_i$ 替换为 $a_i \operatorname{op} x$。 2. 问有多少个不同的 $a_i$ 满足 $l\le a_i\le r$。 $n\le 2\times 10^5,q\le 10^5,a_i,x<2^{20}$ 且 $\mathrm{op}$ 是位运算。 --- 首先 or 可以被其他两种位运算表示出来，所以只需要考虑 and 和 xor。 考虑 xor。拿一颗 trie 树打标记即可。 考虑 and。我们尝试也打标记，具体的： 如果这一位是 $0$ 则把右边合并到左边，否则直接往下传，时间复杂度 $O(n\log^2 V)$。可以通过。 # CF1523H 一个长为 $n$ 的序列 $a_i$，表示当你在 $i$ 的时候可以跳到 $[i,i+a_i]$，$q$ 次查询有 $l,r,k$ 问你在 $[l,r]$ 内删除 $k$ 个点最少要跳几步。 --- 考虑倍增动态规划。设计 $f_{i,j,k}$ 表示从 $i$ 点出发跳了 $2^j$ 步，已经删除了 $k$ 个点的最远距离。 在 $j=0$ 时删除 $k'$ 个点可以跳到 $[i,i+a_i+k']$。而具体跳到哪个点可以线段树处理。 在 $j>0$ 时直接暴力合并两个 $j-1$ 的答案即可。 时间复杂度 $O(nk^2\log n)$，下班！ # CF2018E2 $n$ 个线段，端点是 $1\sim 2n$ 的排列。 问一个最大的子集，使得这个子集可以分成若干组，每组大小相同且一对线段相交当且仅当属于同一组。 $n\le 3\times 10^5$。 --- 按照右端点从小到大的顺序选择，如果这个线段和之前的线段不相交则单开一组。 注意到当我们记录 $f(k)$ 表示一组大小为 $k$ 时能分几组，则 $f(k)\le \dfrac{n}{k}$。 于是我们立马就有一个 $n\sqrt{n\log n}\log n$ 的做法。 现在要维护后缀加，查询全局最大值。 考虑后缀最大值的变化量不超过 $1$，于是只需要维护差分。 后缀加时找到 $<l$ 的最后一个后缀最大值 $+1$ 并改成 $+0$。如果不存在则全局最大值 $+1$，用并查集维护。 时间复杂度 $O(n\sqrt{n\log n}\alpha(n))$。 考虑分治，在两个数相邻的同值域位置暂停分治，对于每一个整除位置都可以分治，此时时间复杂度为 $O(n\sqrt{n}\alpha(n))$。 # CF1707E 给定一个长为 $n$ 的序列 $a_1,\ldots,a_n$，其中对于任意的 $i$ 满足 $1 \leq a_i \leq n$。 定义一个二元组函数如下： $$f((l,r))=(\min\{a_l,\ldots,a_r\},\max\{a_l,\ldots,a_r\})(l \leq r)$$ 你需要回答 $q$ 次询问，每次给定 $(l_i,r_i)$，问其最少经过多少次 $f$ 的调用（即 $(l,r) \rightarrow f((l,r))$）使得 $(l_i,r_i)$ 变成 $(1,n)$，若无解请输出 `-1`。 $n,q\le 10^5$。 --- 某多校联赛场题。搬运知名 3500 真的好吗？？？ 观察到 $f(l,r)=\cup_{i=l}^{r-1}f(i,i+1)$。 接下来考虑推广至 $f^k(l,r)=\cup_{i=l}^{r-1}f^k(i,i+1)$。 首先说明合并时相邻两区间有交。因为当 $[l_1,r_1]$ 和 $[l_2,r_2]$ 有交时 $f(l_1,r_1)$ 和 $f(l_2,r_2)$ 也有交所以是对的。 然后证明原结论。当 $[l_1,r_1]$ 和 $[l_2,r_2]$ 有交时，$f(\min(l_1,l_2),\max(r_1,r_2))$ 显然就是答案。 接下来考虑倍增，预处理 $f^{2^k}(i,i+1)$ 后可以得到 $f^{2^k}(l,r)$，这可以得到 $f^{2^{k+1}}(i,i+1)$。 查询时同样倍增，时间复杂度 $O(n\log^2n+q\log n)$。