「做题记录」Ynoi
stripe_python · · 算法·理论
P6018 [Ynoi2010] Fusion tree
维护一棵
n 个节点的无根树,点有点权a_i 。支持q 次操作:
- 给定
u ,将u 的1- 邻域点权+1 。- 给定
u,\delta ,令a_u \gets a_u - \delta 。保证任意时刻点权非负。- 给定
u ,查询u 的1- 邻域点权异或和。
:::::success[题解]
任意定根后,对每个点
考虑从低位向高位建 01-Trie,支持全局
::::info[01-Trie 全局
考虑二进制下
对应到低位 01-Trie 上,就是自顶向下交换左右儿子,并顺着交换后的左儿子进行递归。复杂度
::::
视
:::::
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[题解]
注意到答案区间
考虑维护长度
复杂度
:::::
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[题解]
以一个
注意到
这样我们就得到了半群信息。注意信息没有交换律,树剖询问时需要按照
得到信息后,从高位向低位贪心,对第
总复杂度
注意到这个 u64 存储,信息合并实现并行计算,复杂度优化到
:::::
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 连续段,区间推平时直接在平衡树上二分出对应区间,然后插入新的连续段。根据颜色段均摊的理论,这个复杂度是对的。
列出
我们用 FHQ 维护维护 01 极长颜色段,修改时仍然二分出对应区间,并用 tag 标记不同段的收缩 / 扩展情况,注意对端点处精细讨论。
这里的颜色段均摊要求极长,所以还需要思考一下实现。比较简单的方案是,平衡树维护颜色段类型和长度,插入新段时前驱后继看是否能合并。注意修改时对两端的颜色段要特殊讨论。
缩段比较复杂,我们需要及时删去长度
区间和则记录额外信息,对每个颜色段讨论它对总和的贡献,标记下传是可以处理的。视
:::::
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 成两段,对
考虑强制在线。注意到函数复合有交换律,这启示我们分块。我们在整块内使用平衡树合并求出
取块长为
注意实现细节,整块预处理要用笛卡尔树式建树,不然复杂度会多
:::::
P6109 [Ynoi2009] rprmq1
维护一个
n \times n 的二维平面,元素初值为0 。先进行m 次 4-side 矩形加,再进行q 次 4-side 矩形查询\max 。
:::::success[题解]
将修改差分为开口向右的 3-side 矩形。视
- 在
l_1 时刻对区间[l_2,r_2] 做加法,r_1+1 时刻对区间[l_2,r_2] 做减法。 - 查询
[l_1,r_1] 时刻内区间[l_2,r_2] 的历史最值。
对时间轴分治,设分治区间
- 执行时刻
[l,m] 中的所有操作。 - 在时刻
m+1 进行重置,此时历史最值更新到当前最值。 - 执行时刻
(m,r] 中的所有操作,并且更新右端点关联的询问。 - 撤销时刻
(m,r] 中的所有操作。此时[1,m] 的操作被正确执行,递归(m,r] 。 - 在时刻
m 进行重置,撤销(m,r] 中的历史最值。 - 撤销时刻
[l,m] 中的所有操作,并且更新左端点关联的询问。此时[1,l) 的操作被正确执行,递归[l,m] 。
使用线段树维护历史
\begin{bmatrix} x&-\infty \ x&0 \end{bmatrix} \begin{bmatrix} M \ H \end{bmatrix}=\begin{bmatrix} M+x \ \max(H,M+x) \end{bmatrix}$。
-
-\infty & 0\\ -\infty & 0 \end{bmatrix} \begin{bmatrix} M \\ H \end{bmatrix}=\begin{bmatrix} H\\ H \end{bmatrix}$。
复杂度
:::::
P5607 [Ynoi2013] 无力回天 NOI2017
维护
n 个集合S_i ,支持n 次操作:
- 给定
i,x ,令S_i \gets S_i \cup \{x\} 。- 给定
i,j ,求|S_i \cup S_j| 。
:::::success[题解]
将
考虑取对偶范围,维护
- 若
|T_x|>B ,我们维护S'_i \subseteq S_i 且S_i' 只包含这样的x 。用 bitset 优化求交,修改O(1) 查询O\left(\dfrac{n}{Bw}\right) 。 - 若
|T_x| \le B ,我们在修改S_i 时直接枚举j \in T_x 并将|S_i \cap S_j| 增加1 。可以用哈希表动态开点地维护(i,j) 对的答案,修改O(B) 查询O(1) 。
可以将询问离线后划分两类
对时空常数的若干优化:
- 预处理出
|T_x| >B 的x 后,将所有x 重标号,这样S_i' 的 bitset 只要开到n/B 大小。 - 对
S_i' 动态开点,当用到S_i' 时再新开 bitset。 - 注意到至多
n 个询问,将询问的(i,j) 离线后离散化,可以将哈希表换成普通数组维护。 - 对于未在询问中出现的
i ,直接忽略S_i \gets S_i \cup \{x\} 的修改。
添加这些优化后足以通过。代码。
:::::
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[题解]
查询
区间加区间排名是经典的分块问题。对序列分块,维护块内元素组成的有序数组。修改时,对散块暴力加后归并重构,整块打标记并标记永久化。查询时,对散块暴力扫,整块二分求答案。
精细实现复杂度
一个小优化是,我们将查询的两段散块归并成一个临时块,查排名时在这个临时块上二分,复杂度优化到
::::::
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 序转化,问题变为
在
:::::info[莫队算法]
将
在可接受的范围内。则可以顺次扫描
常用的构造是,对序列分块后,以
基于这种构造可以得到一种常数优化,若
事实上,莫队有更一般的构造方法。考虑建一张完全图,边
我们可以求出一棵 MST,将 DFS 序作为莫队的转移方向。由于曼哈顿距离满足三角不等式,MST 的代价不超过最优解的
实际上,这个模型还可以进一步扩展。设
:::::
现在考察换根操作。实际上,换根意义下的子树 DFS 序只有
- 若
r=x ,则x 子树 DFS 序为[1,n] 。 - 若
r \notin \text{subtree}(x) ,则x 子树 DFS 序仍为[\text{dfn}_x,\text{dfn}_x+\text{sz}_x) 。注意这里的\text{subtree}(r) 是在r_0 意义下定义的。 - 若
r \in \text{subtree}(x) ,找到x \to r 路径上的第一个节点y ,只要取y 子树的补集,则x 子树 DFS 序为[1,\text{dfn}_y) \cup [\text{dfn}_y+\text{sz}_y,n] 。下图给出了这种情况的一个例子。
在r_0 意义下有\text{dep}_y=\text{dep}_x+1 ,找到r 的\text{dep}_r-\text{dep}_x-1 级祖先即为y ,可以使用树上倍增优化。
对于 DFS 序分段的情况,只需要拆成多个 4-side 矩形并差分。
复杂度
::::::
P5072 [Ynoi Easy Round 2015] 盼君勿忘
给定一个长为
n 的序列a_i ,进行q 次询问,给定l,r,p ,求区间[l,r] 所有子序列分别去重后的总和,对p 取模。
::::::success[题解]
将贡献拆到数值上。设区间长度为
注意到序列中本质不同的
求值时需要计算
:::::info[光速幂]
使用根号平衡计算
取阈值
取
:::::
实际上还有另一种手法,我们将快速幂的查询记忆化,求
由于哈希表操作会被调用
总复杂度
::::::
P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II
给定长为
n 的序列a_i ,进行q 次询问,给定l,r ,查询[l,r] 的逆序对数。
:::::success[题解]
显然有
考虑
将查询
如果直接将询问挂到
对
这个技巧就是俗称的莫队二次离线。
:::::
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[题解]
考虑对询问莫队,数据结构维护值域。设集合
将加法转化为
对于乘法,我们直接枚举
对于除法,我们给出另一种思路。不妨设
扫描线加入
综上所述,本题在
:::::
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 > x ,则块内元素整体-x 。 - 若
B^{k+1} \le x ,则块内元素无变化。 - 若
x \in [B^k,B^{k+1}) ,则需要处理部分块内元素。
对于每块开一棵线段树,下标为原序列的下标,线段树上维护区间和,区间
类似势能线段树地,维护当前内非零数字的个数,在
视
可以使用平衡树代替线段树,空间做到线性但时间常数过大。考虑对线段树底层分块,长度
取略大的
:::::
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[题解]
我们使用定长分块的技巧,将序列每
对于同块的情形容易处理,对每块开线段树支持单点修改,区间最大子段和,半群信息的构造是经典的。查询时散块直接查,整块查询需要对块序列建线段树,维护区间
现在讨论相邻块的处理方法。类似二区间合并地,设前块的后缀和为
转
对于左下开口的 2-side 矩形,其对应
我们用线段树来维护这个分治结构。具体地,对于线段树区间 pushup 时,小三角形可以作为左右儿子递归,而矩形区域内
由于
整块的跨块贡献直接提取根节点答案即可。对于散块,有可能出现区间包含块边界且截断整块的情况,此时的限制形如
这样整个问题得到解决。复杂度
:::::
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[题解]
我们对全局求出
对
复杂度
:::::
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[题解]
我们将
对于每个节点
我们维护
复杂度
:::::info[轻重分离]
不知道这东西有没有名字,算是我自己总结的一个 trick。
对于一类维护
对于树链修改,只有重链切换点的
:::::
::::::
P9058 [Ynoi2004] rpmtdq
给定一棵
n 个节点的无根树,边有边权。进行q 次询问,给定l,r ,查询\min \limits_{l\le i < j \le r} \text{dis}(i,j) 。
:::::success[题解]
转
根据第二类支配对的理论,考虑对信息维分治。直接拆开
记
我们将子树按
最后的问题是 2-side 矩形数点,扫描线树状数组即可。复杂度
:::::