「做题记录」Ynoi

· · 算法·理论

P6018 [Ynoi2010] Fusion tree

维护一棵 n 个节点的无根树,点有点权 a_i。支持 q 次操作:

  • 给定 u,将 u 的 1- 邻域点权 +1。
  • 给定 u,\delta,令 a_u \gets a_u - \delta。保证任意时刻点权非负。
  • 给定 u,查询 u 的 1- 邻域点权异或和。

:::::success[题解]

任意定根后,对每个点 u 维护儿子点权组成的数据结构,父亲的信息单独处理。

考虑从低位向高位建 01-Trie,支持全局 +1,单点修改,全局异或和,邻域修改 & 查询时单独处理父亲的信息即可。

::::info[01-Trie 全局 +1]

考虑二进制下 +1 的过程,实际上是从低位向高位取反,若取反后为 0 则继续考虑下一位。

对应到低位 01-Trie 上,就是自顶向下交换左右儿子,并顺着交换后的左儿子进行递归。复杂度 O(\log V)。

::::

视 n,q,V 同阶复杂度 O(n \log n)。

:::::

P12013 [Ynoi April Fool's Round 2025] 牢夸

维护一个长为 n 的序列 a_i,支持 q 次操作:

  • 给定 l,r,\delta,对 i \in [l,r] 令 a_i \gets a_i+\delta。
  • 给定 l,r,查询 \max \limits_{[L, R] \subseteq [l, r]\land L \ne R} \frac{\sum \limits_{i=L}^{R} a_i}{R-L+1}。

:::::success[题解]

注意到答案区间 [L,R] 的长度 \le 3。证明考虑调整法,从区间中分出一段长度 =2 的区间,则两段都不劣于原权值,对较长区间归纳即得。

考虑维护长度 \le 3 的子区间的区间和。构造半群信息时,需要维护端点处开始的 \le 2 个数的和,对跨越中点的子区间精细讨论。区间加打标记处理,询问求出 =2 和 =3 的最大平均数取 \max 即可。

复杂度 O(q \log n)。

:::::

P5354 [Ynoi Easy Round 2017] 由乃的 OJ

维护一棵 n 个点的无根树,第 i 个节点有函数 f_i(x),为 f_i(x)=x \text{ and } a_i 或 x \text { or } a_i 或 x \oplus a_i 之一。支持 q 次操作:

  • 给定 u,v,k,求 \max \limits_{x \in [0,k]} (f_v \circ \cdots \circ f_u)(x)。
  • 给定 u,f_u,将 u 点的函数改为 f_u。

:::::success[题解]

以一个 \log 的代价,使用重链剖分拍到序列上。

注意到 f 只有位运算,对每个二进制位独立,考虑拆位处理。线段树节点维护两个 64 位数组,表示第 i 个二进制位初始为 0/1 时,区间复合函数的点值,信息可以合并。

这样我们就得到了半群信息。注意信息没有交换律,树剖询问时需要按照 u \to v 的方向跳重链,线段树上还要维护反串信息。

得到信息后,从高位向低位贪心,对第 d 位,若填 0 得 1 则最优,否则若 k \ge 2^d 且填 1 得 1 则令 k \gets k-2^d。

总复杂度 O(n \log^2 n \log V) 难以通过。

注意到这个 64 位数组的值域为 \{0,1\},考虑直接压成 u64 存储,信息合并实现并行计算,复杂度优化到 O\left(n\log^2 n \dfrac{\log V}{w}\right),可以视作去掉了 \log V。代码。

:::::

P5066 [Ynoi Easy Round 2014] 人人本着正义之名

维护长为 n 的 01 序列 a_i,支持 q 次操作:

  • 给定 l,r,对 i \in [l,r] 令 a_i \gets 0。
  • 给定 l,r,对 i \in [l,r] 令 a_i \gets 1。
  • 给定 l,r,对 i \in [l,r) 令 a_i \gets a_i \text { and } a_{i+1},所有数同步操作。
  • 给定 l,r,对 i \in [l,r) 令 a_i \gets a_i \text { or } a_{i+1},所有数同步操作。
  • 给定 l,r,对 i \in (l,r] 令 a_i \gets a_i \text { and } a_{i-1},所有数同步操作。
  • 给定 l,r,对 i \in (l,r] 令 a_i \gets a_i \text { or } a_{i-1},所有数同步操作。
  • 给定 l,r,求 \sum \limits_{i=l}^r a_i。

强制在线。

:::::success[题解]

考虑用 FHQ 维护 01 连续段,区间推平时直接在平衡树上二分出对应区间,然后插入新的连续段。根据颜色段均摊的理论,这个复杂度是对的。

列出 \text{and} 和 \text{or} 运算的真值表,可以得到题目四种操作的本质:

我们用 FHQ 维护维护 01 极长颜色段,修改时仍然二分出对应区间,并用 tag 标记不同段的收缩 / 扩展情况,注意对端点处精细讨论。

这里的颜色段均摊要求极长,所以还需要思考一下实现。比较简单的方案是,平衡树维护颜色段类型和长度,插入新段时前驱后继看是否能合并。注意修改时对两端的颜色段要特殊讨论。

缩段比较复杂,我们需要及时删去长度 \le 0 的段并合并两侧。考虑 FHQ 上维护节点长度的 \min,暴力递归整树对失效段重构,长度 \min \ge 1 就剪枝,势能分析下来复杂度是对的。

区间和则记录额外信息,对每个颜色段讨论它对总和的贡献,标记下传是可以处理的。视 n,q 同阶复杂度 O(n \log n)。代码。

:::::

P8264 [Ynoi Easy Round 2020] TEST_100

给定长为 n 的序列 a_i,q 次询问给定 l,r,v,查询

(f_r \circ f_{r-1} \circ \cdots \circ f_{l})(v)

其中 f_i(x)=|x-a_i|。强制在线。

:::::success[题解]

考虑允许离线怎么做。使用插入—标记—回收算法配合 FHQ-Treap,在标记时 split 成两段,对 [1,a_i] 取相反数并加上 a_i,对 (a_i,+\infty) 减去 a_i,再将两棵树有交合并。

考虑强制在线。注意到函数复合有交换律,这启示我们分块。我们在整块内使用平衡树合并求出 1 \sim V 每个数变成了什么,询问时散块暴力,整块使用预处理的信息。

取块长为 \sqrt{n} 复杂度平衡,视 n,q,V 同阶为 O(n\sqrt{n})。

注意实现细节,整块预处理要用笛卡尔树式建树,不然复杂度会多 \log。整块处理常数过大,我的实现取块长 B=3 \times 10^3 最快。代码。

:::::

P6109 [Ynoi2009] rprmq1

维护一个 n \times n 的二维平面,元素初值为 0。先进行 m 次 4-side 矩形加,再进行 q 次 4-side 矩形查询 \max。

:::::success[题解]

将修改差分为开口向右的 3-side 矩形。视 x 轴为时间轴,题意可以转化为:

对时间轴分治,设分治区间 [l,r] 与分治中心 m,我们只处理跨过 m 的询问。注意分治顺序的问题,下面给出正确的算法流程:

使用线段树维护历史 \max,支持区间加和区间重置。用 (\max,+) 矩阵构造半群,设当前最值 M,历史最值 H,信息设计为向量 $ \begin{bmatrix} M \ H \end{bmatrix}

-

\begin{bmatrix} x&-\infty \ x&0 \end{bmatrix} \begin{bmatrix} M \ H \end{bmatrix}=\begin{bmatrix} M+x \ \max(H,M+x) \end{bmatrix}$。

复杂度 O(2^3n \log^2 n+2^3 q \log n)。

:::::

P5607 [Ynoi2013] 无力回天 NOI2017

维护 n 个集合 S_i,支持 n 次操作:

  • 给定 i,x,令 S_i \gets S_i \cup \{x\}。
  • 给定 i,j,求 |S_i \cup S_j|。

:::::success[题解]

将 |S_i \cup S_j| 容斥为 |S_i|+|S_j|-|S_i\cap S_j|,问题转化为求集合交。直接维护每个 S_i,复杂度难以低于 O\left(\dfrac{n^2}{w}\right)。

考虑取对偶范围,维护 T_x=\{i \mid x \in S_i\}。我们对 |T_x| 阈值分治,设阈值为 B,则 |T_x|>B 的 x 至多 \dfrac{n}{B} 个。

可以将询问离线后划分两类 x。取 B=\sqrt{\dfrac{n}{w}} 得最优复杂度 O\left(\dfrac{n^{1.5}}{\sqrt{w}}\right)。

对时空常数的若干优化:

添加这些优化后足以通过。代码。

:::::

P5356 [Ynoi Easy Round 2017] 由乃打扑克

维护长为 n 的序列 a_i,支持 q 次操作:

  • 给定 l,r,\delta,对 i \in [l,r] 令 a_i \gets a_i+\delta。
  • 给定 l,r,k,求 [l,r] 中的第 k 小值。

::::::success[题解]

查询 k 小值考虑对值域二分,将问题转化为查询排名。

区间加区间排名是经典的分块问题。对序列分块,维护块内元素组成的有序数组。修改时,对散块暴力加后归并重构,整块打标记并标记永久化。查询时,对散块暴力扫,整块二分求答案。

精细实现复杂度 O(n \sqrt{n \log n} \log V),通过需要一些手法。

一个小优化是,我们将查询的两段散块归并成一个临时块,查排名时在这个临时块上二分,复杂度优化到 O(n\sqrt{n} \log V)。

::::::

P4689 [Ynoi Easy Round 2016] 这是我自己的发明

维护节点数为 n 的有根树,点有点权 a_i。支持 q 次操作:

  • 给定 u,将树根换为 u。
  • 给定 u,v,查询满足 x \in \text{subtree}(u) \land y \in \text{subtree}(v) 且 a_x=a_y 的 (x,y) 对数。

::::::success[题解]

只考虑查询操作。子树条件可以用 DFS 序转化,问题变为 x \in [l_1,r_1] \land y \in [l_2,r_2] \land a_x=a_y 的 (x,y) 对数。

在 l-r 二维平面上,(x,y) 的范围是 4-side 矩形,将其差分为 2-side,则只要对 x \le l\land y \le r 求 a_x=a_y 的数目。这是经典的莫队问题,用桶配合普通莫队即可解决。

:::::info[莫队算法]

将 q 次询问 [l_i,r_i] 离线,并按照某种特殊方式排序,使得

\sum_{i=2}^q (|l_i-l_{i-1}|+ |r_i-r_{i-1}|)

在可接受的范围内。则可以顺次扫描 [l_1,r_1] \sim [l_n,r_n],用指针维护当前的 l,r,在指针移动的过程中更新数据结构,由于指针会扩展和收缩,数据结构需要支持插入删除。

常用的构造是,对序列分块后,以 l_i 所在块编号为第一关键字,r_i 的大小为第二关键字排序,可以证明复杂度 O(n \sqrt{q}+q \log q)。

基于这种构造可以得到一种常数优化,若 l_i 所在块编号为奇数,则按 r_i 升序,否则按 r_i 降序,这个构造称作奇偶性排序,一般比上面的构造略快。

事实上,莫队有更一般的构造方法。考虑建一张完全图,边 i \to j 的边权为 |l_i-l_{i-1}|+ |r_i-r_{i-1}|,问题转化为找到最小 Hamilton 路。

我们可以求出一棵 MST,将 DFS 序作为莫队的转移方向。由于曼哈顿距离满足三角不等式,MST 的代价不超过最优解的 2 倍。

实际上,这个模型还可以进一步扩展。设 q 次查询的范围为 S_i,我们希望重排 S_1 \sim S_q 最小化 |S_1|+\sum \limits_{i=2}^{q} |S_i \triangle S_{i-1}|,其中 \triangle 是集合对称差。我们仍可以构造完全图求 MST,根据对称差的三角不等式,这可以得到常数倍近似的普通莫队转移代价。

:::::

现在考察换根操作。实际上,换根意义下的子树 DFS 序只有 \le 2 段。设原树根为 r_0,在 r_0 意义下求 DFS 序后,当前树根换为 r,讨论 x 子树的 DFS 序:

对于 DFS 序分段的情况,只需要拆成多个 4-side 矩形并差分。

复杂度 O(n \sqrt{q} +q \log q)。代码。

::::::

P5072 [Ynoi Easy Round 2015] 盼君勿忘

给定一个长为 n 的序列 a_i,进行 q 次询问,给定 l,r,p,求区间 [l,r] 所有子序列分别去重后的总和,对 p 取模。

::::::success[题解]

将贡献拆到数值上。设区间长度为 m,数字 x 出现 k 次,只要在 k 个位置中选择至少一个,方案数 2^m-2^{m-k}。记出现 k 次的数的总和为 f(k),答案为 \sum \limits_{k=0}^m f(k) \times (2^m-2^{m-k})。

注意到序列中本质不同的 k 至多 \sqrt{n} 种,直接使用 Hash 表维护 f,询问时扫描整表进行求值即可。

求值时需要计算 2^{m-k} \bmod p,使用 O(1) - O(\log m) 的快速幂会得到 O(\sqrt{m} \log m) 的复杂度。可以使用 O(\sqrt{m})-O(1) 的光速幂进行平衡。

:::::info[光速幂]

使用根号平衡计算 a^n \bmod p 的 trick,其中 a,p 固定。

取阈值 B,在 p 意义下递推出 a^1, a^2,\cdots, a^B 和 a^{2B}, a^{3B},\cdots,a^{B^2}。设 n=xB+y,则 a^n \equiv a^{xB} \times a^y。

取 B=O(\sqrt{n}) 则复杂度 O(\sqrt{n})-O(1)。实际上,取 B=O(\sqrt[k]{n}) 可以得到 O(kB)-O(k) 的复杂度。

:::::

实际上还有另一种手法,我们将快速幂的查询记忆化,求 2^x \bmod p 时找到 y \le x 且最大的 y,只要倍增 2^{x-y} \bmod p,复杂度 O(\log (x-y))。应用微积分知识可以证明复杂度是单根号的。

由于哈希表操作会被调用 O(n \sqrt{q}) 次,常数过大而无法通过。我们可以用双向链表维护有值位置,将哈希表改成普通数组减少常数。

总复杂度 O(n \sqrt{q}+q \sqrt{n})。代码。

::::::

P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II

给定长为 n 的序列 a_i,进行 q 次询问,给定 l,r,查询 [l,r] 的逆序对数。

:::::success[题解]

显然有 O(n\sqrt{q} \log n) 的做法,在莫队指针移动时,对值域维护树状数组,容易更新逆序对数。

考虑 [l,r] \to [l,r+1] 转移时,需要在 [l,r] 中查询 x=a_{r+1} 的区间排名。转 i-a_i 二维平面分析,则查询是 3-side 矩形数点,我们将其差分为 2-side。

将查询 (l,r,x) 全部离线下来,对 x 轴扫描线,则 y 轴上的数据结构需要 O(n) 次插入和 O(n\sqrt{q}) 次查询。使用 O(\sqrt{n}) - O(1) 的分块平衡,整个问题复杂度 O(n^{1.5}+n\sqrt{q})。

如果直接将询问挂到 x 轴上,空间是 O(n\sqrt{q}) 的。我们考察 r 指针从 r_1 \to r_2 的贡献为,对每个 i \in (r_1,r_2],a_i 对 [l,i) 的逆序对数。将 [l,i) 差分为 [1,i) 减去 [1,l),则 a_i 在 [1,i) 的贡献可以预处理。

对 i \in (r_1,r_2],原算法将 a_i 逐个挂到 l-1 位置上。可以发现,挂到 l-1 的 a_i 是若干连续段,可以直接存下 (r_1,r_2] 作为查询,扫描线时暴力扫连续段更新询问。时间不变的情况下,空间降低到 O(n)。

这个技巧就是俗称的莫队二次离线。

:::::

P5355 [Ynoi Easy Round 2017] 由乃的玉米田

给定长为 n 的序列 a_i,支持 q 次操作:

  • 给定 l,r,x,判定 \exists i,j \in [l,r], a_i+a_j=x。
  • 给定 l,r,x,判定 \exists i,j \in [l,r],a_i-a_j=x。
  • 给定 l,r,x,判定 \exists i,j \in [l,r],a_i\times a_j=x。
  • 给定 l,r,x,判定 \exists i, j \in [l,r], \frac{a_j}{a_i}=x。

:::::success[题解]

考虑对询问莫队,数据结构维护值域。设集合 S=\{a_i \mid i \in [l,r]\},若 S 与 S 平移 x 位的数集有交,则 \exists i,j\in[l,r],a_i-a_j=x。可以用 bitset 优化。

将加法转化为 a_i=x-a_j,可以对 -a_j 维护另一个数集 T。放到 bitset 时要对下标偏移 +V。

对于乘法,我们直接枚举 x 的因数 d,判断 d \in S \land x/d \in S 是否成立。用调和型枚举预处理因数后,复杂度 O(d(V))。

对于除法,我们给出另一种思路。不妨设 i \le j,离线对 r 升序扫描线,对每个 x 维护 f_x 表示最大的 i 满足 \exists j \in [i,r],x \times a_i=a_j,只要判断 f_r \ge l 即可。

扫描线加入 a_r 时,枚举 a_r 的因数 d,用 d 最后出现的位置更新 f_{a_r/d} 即可。若 i>j 只要倒着扫描线,复杂度 O(d(V))。

综上所述,本题在 O\left(V \log V+n\sqrt{q}+\dfrac{qV}{w}+(n+q) \times d(V)\right) 内得到解决。代码。

:::::

P7447 [Ynoi2007] rgxsxrs

维护长为 n 的序列 a_i,支持 q 次操作:

  • 给定 l,r,x,对 i \in [l,r] 若 a_i>x 则令 a_i \gets a_i -x。
  • 给定 l,r,同时求出 [l,r] 的和,最小值,最大值。

强制在线。

:::::success[题解]

我们使用倍增值域分块,将 [B^k,B^{k+1}) 中的数分到一块,得到 \log_B V 块。修改时:

对于每块开一棵线段树,下标为原序列的下标,线段树上维护区间和,区间 \max 和区间 \min。考虑三种块怎么修改:

类似势能线段树地,维护当前内非零数字的个数,在 \text{max} \le x 或区间为空时剪枝。注意到跌落只会执行 \log_b V 次,均摊复杂度是对的。

视 n,q 同阶,复杂度可以分析到 O\left(n\dfrac{B}{\log B} \log n\log V\right),空间 O(n \log_B V)。实现。

可以使用平衡树代替线段树,空间做到线性但时间常数过大。考虑对线段树底层分块,长度 \le \log n 的节点直接暴力,时间不变的情况下空间优化到线性。

取略大的 B 以平衡时空常数,微调底层分块的阈值后可以通过。我的实现取 B=14,对底层按 16 分块可稳定通过。代码。

:::::

P6780 [Ynoi2009] pmrllcsrms

给定常数 C。维护长为 n 的序列 a_i,支持 q 次操作:

  • 给定 i,x,令 a_i \gets x。
  • 给定 l,r,求 \max\left(0,\max \limits_{[x,y] \subseteq [l,r] \land y-x+1 \le C} \sum \limits_{i=x}^y a_i\right)。

:::::success[题解]

我们使用定长分块的技巧,将序列每 C 个元素分到一块,则答案区间只能在同块内,或者在相邻两块内。

对于同块的情形容易处理,对每块开线段树支持单点修改,区间最大子段和,半群信息的构造是经典的。查询时散块直接查,整块查询需要对块序列建线段树,维护区间 \max 快速求值。

现在讨论相邻块的处理方法。类似二区间合并地,设前块的后缀和为 a_i,后块的前缀和为 b_i,则答案可以表示为 \max \limits_{i+j \le C} (a_i+b_j)。

转 i-j 二维平面分析,则每个点 (i,j) 带权 a_i+b_j,查询是对 i+j \le C 这个直角三角形区域数点。

对于左下开口的 2-side 矩形,其对应 i \le x \land j \le y 的限制,i,j 独立,求解是容易的。这启发我们从直角三角形中划出一个矩形,分成矩形和两个小直角三角形进行维护,而小的三角形可以继续递归:

我们用线段树来维护这个分治结构。具体地,对于线段树区间 [l,r],我们令其表示 i \in [l,r] \land j \in [C-r,C-l] 的直角三角形。对 [l,r] 做 pushup 时,小三角形可以作为左右儿子递归,而矩形区域内 i,j 独立,分别维护 a_i 和 b_j 的 \max 即可。对三个区域的答案求 \max 即为当前节点的答案。

由于 a,b 是前后缀和,故修改是对 a,b 的区间加减。我们维护的信息只有 \max a, \max b 和区域内答案,则修改是容易用标记解决的。

整块的跨块贡献直接提取根节点答案即可。对于散块,有可能出现区间包含块边界且截断整块的情况,此时的限制形如 i \le x \land j \le y \land i+j \le C,可能是矩形 / 梯形 / 五边形区域。我们都可以划分为若干矩形和若干三角形得到答案:

这样整个问题得到解决。复杂度 O(q \log n)。

:::::

P8511 [Ynoi Easy Round 2021] TEST_68

给定一棵 n 个点的有根树,根节点为 1,点有点权 a_i。对每个 x=1,2,\cdots,n 求

\max _{u,v \notin \text{subtree}(x)} (a_u \oplus a_v)

:::::success[题解]

我们对全局求出 \max \limits_{u ,v} (a_u \oplus a_v),则 u \to v 树链下的节点对应答案必为 a_u \oplus a_v。

对 1 \to u 和 1 \to v 根链上的节点,其答案需要单独计算。我们自顶向下地扫描根链,在 01-Trie 上贪心求出答案,并插入当前点的点权即可。

复杂度 O(n \log V)。

:::::

P5314 [Ynoi2011] ODT

维护一棵节点数为 n 的无根树,点有点权 a_i,支持 q 次操作:

  • 给定 u,v,\delta,对 (u,v) 树链上的节点 x 令 a_x \gets a_x + \delta。
  • 给定 u,k,求 u 的 1- 邻域中第 k 小点权。

::::::success[题解]

我们将 1- 邻域划分为父亲 / 重儿子 / 轻儿子分别维护。

对于每个节点 u,维护其所有轻儿子点权构成的平衡树 T_u=\{a_v \mid v \in \text{lson}(u)\}。做树链加法时,只有在重链的切换点才需要修改 T_u,而切换点的数目是 O(\log n) 的。

我们维护 a 序列,支持树链加单点查询,树剖套树状数组即可。询问是查询 T_u \cup \{a_u, a_{\text{fa}(u)}, a_{\text{hson}(u)}\} 的第 k 小,先插入后删除即可。

复杂度 O(q \log^2 n),贺一个高速平衡树跑的飞快。代码。

:::::info[轻重分离]

不知道这东西有没有名字,算是我自己总结的一个 trick。

对于一类维护 S_u=\{a_v \mid v \in \text{son}(u)\} 的问题,我们分别维护 S_u'=\{a_v \mid v \in \text{lson}(u)\} 和 a_{\text{hson}(u)}。

对于树链修改,只有重链切换点的 S_u' 会改变,可以暴力修改。在每条重链上,只要维护连续的 a_u,a_{\text{hson}(u)}, \cdots 序列,可以开序列数据结构维护。

:::::

::::::

P9058 [Ynoi2004] rpmtdq

给定一棵 n 个节点的无根树,边有边权。进行 q 次询问,给定 l,r,查询 \min \limits_{l\le i < j \le r} \text{dis}(i,j)。

:::::success[题解]

转 l-r 二维平面分析,将点对 (i,j) 的权值视作 \text{dis}(i,j),询问是 2-side 矩形求 \min,但点对数量不可接受。

根据第二类支配对的理论,考虑对信息维分治。直接拆开 \text{dis} 会涉及 LCA 深度,这启发我们任意定根后,用点分治的方法枚举 LCA 为 x,钦定 \text{lca}(i,j)=x 后在 x 子树内求支配对。

记 \text{dis}(u,x)=f_u。考察三点 i<j<k,则 (i,k) 被 (i,j) 支配的条件为 f_j \le f_k。取固定的 k,求出点集 S=\{u \mid f_u \le f_k\},则 k 与它在 S 中的前驱后继形成了支配对。

我们将子树按 f 升序排序并扫描,用一个 std::set 维护已扫描点的标号,扫到 u 时查询其前驱后继作为支配对即可。

最后的问题是 2-side 矩形数点,扫描线树状数组即可。复杂度 O(n \log^2 n+q \log n)。代码。

:::::