Ynoi 部分选做

· · 个人记录

太阳升太阳落 木叶吹起山火

暴雨洗刷泥河 只有风带着伤痕回来

太阳落月亮升 旧石头化成风

只有永久一动不动

可能会持续更新，也可能不会。

P4117 [Ynoi2018] 五彩斑斓的世界

序列分块，对每块独立维护。考虑整块操作，也即全局操作时的情况。对值域维护数组 a 表示值为 i 的数有 a_i 个。考虑势能 \max-\min，注意到每次操作后势能减少 \min\{\max-x,x-\min\}。考虑对于两个类型各给出一个做法：\max-x 可以对于所有 \geq x 的减去 x，操作后必 \max\leq x。x-\min 可以对于所有 \leq x 的加上 x，然后对所有数 -x，操作后必 \min\geq x（不算全局减） 。

加上散块操作时由于需要查询对应位置的真实值，由于操作过程中只涉及到不同值的合并，我们用对每个块一个并查集维护所有值的等价类关系即可。

时间复杂度 \Omicron(n\sqrt n\alpha(n))。

P4118 [Ynoi2018] 末日时在做什么？有没有空？可以来拯救吗？

考虑弱化弱化问题，全局加全局最大子段和。全局加相当于给全局加一个偏移量 x，而此时一个区间的和相当于一个关于 x 的一次函数。而最大子段和为所有区间和的 max，故其下凸。根据最大子段和经典 trick，信息具有可合并性， f_{l,r}=\max \{f_{l,k},f_{k+1,r},g_{k+1,r}+h_{l,k}\}。由于 f,g,h 均关于 x 下凸，分治维护凸包做闵可夫斯基和即可。

考虑弱化问题，全局加区间最大子段和。注意到我们已经有了线段树上每个节点代表区间的 f_x,g_x,h_x，将区间拆分为 \Omicron(\log n) 个节点直接合并即可。

考虑原问题，区间加区间最大子段和。考虑分块，对每个块求出凸壳，修改时散块重构、整块打 tag，查询时散块暴力、整块查表。暴力做如上过程时间复杂度 \Omicron(n\sqrt{n}\log n)，需做出以下两个优化：

  1. 修改时散块不重构，而是直接在线段树上做区间加，容易发现时间复杂度 \Omicron(B)。
  2. 查询时将询问离线下来排序，可以省去整块查表时二分所需的 \log。

时间复杂度 \Omicron(n\sqrt n)。

P4119 [Ynoi2018] 未来日记

修改相信在 2025 年大家已经十分熟悉了。对序列分块，块内维护并查集表示值的映射关系，这样就可以简单的实时求出每个点的颜色。考虑查询怎么做。

区间 k 小值，考虑对值域分块，相邻 \sqrt{V} 个数合并到一起。修改时维护一下前 i 个（序列）块中值（压缩后）为 j 的个数。查询时从小到大枚举确定答案所在（值域）块。随后同理维护前 i 个（序列）块中值（压缩前）为 j 的个数，查询时扫一遍即可。

时间复杂度 \Omicron(n\sqrt n\alpha(n))。

P5397 [Ynoi2018] 天降之物

做法与上一题类似但更加简单，原因在于序列中的值等价于颜色。所以修改时若不改变块内等价类形态时，也即不涉及颜色合并时，该修改对本块无效。故总共只有 \Omicron(n) 次有效单块修改。单块修改指一个块内的修改。

考虑配合上查询，对序列分块，查询时希望预处理好每一块的答案，同时支持块间贡献的计算。对每一个块维护 f_{i,j} 表示颜色 i 对颜色 j 的贡献，以及 pre_i/lst_i 表示颜色 i 第一次 / 最后一次的位置。由于单块修改只有 \Omicron(n) 次，对所有与涉及颜色相关的贡献全部重算即可。

时间复杂度 \Omicron(n\sqrt n\alpha(n))。

P5398 [Ynoi2018] GOSICK

对值域根号分治。大数对大数考虑莫队+二次离线，修改时对所有 a_i 的倍数和因数贡献 +1，查询时查询单点值即可。小数由于其只有 \Omicron(\sqrt n) 种，考虑对每种数直接计算出答案。注意到其贡献为区间中 x 的个数以及 x 倍数个数的积。对每种数 x 维护所有前缀中 x 的个数以及 x 的倍数个数。查询时枚举所有小数计算贡献即可。

时间复杂度 \Omicron(n\sqrt n)。

P5399 [Ynoi2018] 駄作

top cluster 分块模板。考虑两个点的距离如何计算：与序列分块类似，当两个点在同一块内时，直接预处理，记为类型 A。否则找到路径上所有整块，计算两个界点之间的距离，记为类型 B；找到路径上两个半整块，计算端点到两个界点之间的距离，记为类型 C。

考虑处理询问，把贡献摊到每个块上计算。每个邻域在一个块内有三种表现方式：任意邻域、界点邻域、全集。将全集归入界点邻域。考虑计算 A 类贡献：对于一组询问，任意邻域只会出现 \Omicron(1) 次，把贡献摊到边上即可。否则一定形如两个界点邻域算贡献，直接预处理所有界点邻域对算贡献。考虑计算 B 类贡献：每一个点对贡献均为界点距离，直接算点对个数即可。C 类贡献与 B 类贡献类似不细说。

总结：对每个块维护界点邻域（到界点距离总和）、界点邻域对贡献、两界点距离。完事。

时间复杂度 \Omicron(n\sqrt n)。

P6578 [Ynoi2019] 魔法少女网站

分块，对每个块维护块内的所有答案，以及每个块 \leq x 的最长前后缀。单点修改时重构整块，建出笛卡尔树，问题变为一堆区间赋值单点查询。带 \log 做法容易不细说。由于问题本质上是在序列上做快速二分，考虑分散层叠，在多序列上共同二分，把 sqrt 上的 \log 扔掉。

洛谷题解还指出了另外一种做法，注意到静态时可以通过对询问排序把二分的 log 扔掉。故考虑根号重构，对每块询问排序，其余做法类似。

时间复杂度 \Omicron(n\sqrt n)。

P6579 [Ynoi2019] Happy Sugar Life

任意矩形看起来很蠢，对 x 轴分块，计算所有散块贡献。散块上每个点贡献形如二维数点，拼一个 \Omicron(\sqrt n)-\Omicron(1) 的二维数点即可。

对于一组询问 (l,r,L,R)，其中 l,r 为整块端点，将其改为 (l,r,1,R) 的答案减去 [l,r,1,L-1] 里的点对 [l,r,L,R] 点的贡献。前者我们考虑固定 r，对每个 r 分别统计，此时每个点的贡献即为他右下的点个数，问题转为二维数点。拼一个 \Omicron(1)-\Omicron(\sqrt n) 的二维数点即可。后者我们考虑第 i 个块对第 j 个块的贡献。当 i\neq j 时，贡献即为 [i,L,R] 的点数乘以 [j,1,L-1] 的点数，容易转为 \Omicron(n\sqrt n) 次二维数点。当 i=j 时，由于每个块里只有 \Omicron(\sqrt n) 个数，所以只有 \Omicron(n) 个本质不同的区间。所有区间的答案可以 \Omicron(n) 算出。查询时查表即可。注意查表时不需要二分在表中的位置，可以开个桶记录每个点位置。

时间复杂度 \Omicron(n\sqrt n)。

P6580 [Ynoi2019] 美好的每一天~ 不连续的存在

不会做。

P11365 [Ynoi2024] 新本格魔法少女りすか

多区间拼接逆序对。序列分块，把区间拆成 B 个单点和 \frac{n}{B} 个整块。考虑计算整块对所有的贡献。可以计算出每个整块对每个前缀的贡献。随后就可以 \Omicron(k) 计算出整块对所有区间的贡献，时间复杂度 \Omicron(\frac{n}{B}\times k)。计算散块对散块的贡献，由于散点一共只有 \Omicron(kB) 个，可以做到 \Omicron(kB\log n)。

时间复杂度 \Omicron(n\sqrt{n\log n})。

P11366 [Ynoi2024] 末日的魔法少女计划

时间复杂度 ？？？。 #### P11367 [Ynoi2024] 魔法少女网站第二部 首先有一种莫队做法，维护新插入/删除点的前驱后继，时间复杂度 $\Omicron(n\sqrt n\log n)$，由于只删除可以用链表维护前驱后继，所以可以把 $\log$ 干掉。 但这个题其实可以 n*polylog。考虑 cdq 分治。对于询问 $[l,r]$，考虑对所有位置 $i$ 计算 $i$ 对 $i$ 到 $pre_i/nxt_i$ 的贡献。注意到 $i$ 和 $j$ 的贡献为 $|i-j|$，故只需要关心 $i$ 和 $j$ 的位置关系即可。 首先固定 $r$。不妨假设 $i>mid$。可以求出 $nxt'_i$ 表示 $i$ 在 $[mid+1,r]$ 的后继。若 $nxt_i>mid$，则 $nxt_i=nxt'_i$，否则 $nxt_i$ 必然在 $i$ 以左。$nxt_i>mid$ 当且仅当 $[l,mid]$ 不存在 $a_i$ 属于 $[a_i,a_{nxt'_i}]$。此时合法的 $l$ 是个后缀。此时所有贡献已经都可计算。我们对 $r$ 扫描线，注意到所有的 $nxt'$ 只会更改 $\Omicron(n)$ 次。故可以直接维护。 时间复杂度 $\Omicron(n\log^2n)$。听说可以 $/\text{loglog}$，但我不会。 #### P11368 [Ynoi2024] After god 是不是涉及前缀信息的玩意都可以扫下标？ 对下标扫描线，维护每个时刻的答案。维护：区间 $a_i$ 赋值，全局 $b_i$ 加 $a_i$ 历史 $\max$，单点查 $b_i$ 历史和。注意到转移形如 $(\max,+)$ 矩阵乘法，具有结合律，可以线段树维护。 时间复杂度 $\Omicron(n\log n)$。 #### P11369 [Ynoi2024] 弥留之国的爱丽丝 说句闲话，recall 之前把这个题看了，于是省选苟了一命。 离线对时间分块。每块里只有 $B$ 条边的颜色待定。先对其他边缩点，时间复杂度 $\Omicron(\frac{n^2}{B})$。我们只关心询问涉及到的点和修改的边的端点。也即只有 $\Omicron(B)$ 个点是有用的。求出这些点的传递闭包，时间复杂度 $\Omicron(\frac{n}{B}\times n\times \frac{B}{w})=\Omicron(\frac{n^2}{w})$。随后每次查询时我们直接跑一遍 dfs，这里依然可以压位。时间复杂度 $\Omicron(n\times \frac{B^2}{w})$。平衡一下即可。 时间复杂度 $\Omicron(n^2\times w^{-1}+n^{\frac{5}{3}}\times w^{-\frac{1}{3}})$。 #### P11370 [Ynoi2024] 堕天作战/虚空处刑 不会做。