专栏文章

Ynoi根号部分杂谈

yyzq_yzq
个人记录参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqyncjc
此快照首次捕获于
2025/12/04 12:53
3 个月前
此快照最后确认于
2025/12/04 12:53
3 个月前
查看原文
静态区间逆序对，区间众数

P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I

强制在线区间逆序对，做法是预处理，然后整块散块分开算贡献，复杂度刚好平衡，常数很大，比较卡常。

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

区间逆序对离线做法，二次离线模板，常数很小也比序列分块好写。

P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III

区间众数，特别小清新的分块，常数很小， n=5×105n=5\times10^5 2s 稳过。
当然具体用到区间逆序对，众数的时候往往并不完全是板子，需要很多细节处理。

P7882 [Ynoi2006] rsrams

题意就是求一个区间的所有子区间的绝对众数之和，如果没有绝对众数那么那个区间绝对众数就是 0。
对于判断一个数 cc 是否能成为一个区间的绝对众数，我们可以把所有为 cc 的位置赋值成 1，其他赋值成 -1，一个区间绝对众数是 cc 当且仅当区间和大于 0。
做个前缀和过后不难发现问题变成求区间顺序对数。
考虑对颜色出现次数根号分治。
cnt≤Bcnt \leq B ，cc 成为绝对众数的区间是 cnt2cnt^2 级别的，把这些区间取出来做分块的二维数点即可。
cnt>Bcnt > B ，直接二次离线莫队是会死的，因为这相当于把原问题加强了，不难发现 ∣si−si−1∣≤1|s_i - s_{i-1}| \leq 1 ，于是用个桶普通莫队就行，但是序列长度还是 nn ，于是还得优化，把 n′n' 降到 cntcnt 级别。
1 的个数是与 cntcnt 相同的，考虑对每个 1 找前边，后边的第一个 -1，然后构造一个等价的新序列，不难发现新序列长度 n′≤3cntn' \leq 3cnt ，做 n′mn'\sqrt m 的莫队就行了。

P7448 [Ynoi2007] rdiq

主要讲述了 nb 的二维数组 O(n)O(\sqrt n) 单点加，O(1)O(1) 二维求和。
这个题直接二离套用这个就行了，做法跟博丽灵梦差不多的。
还有个经典的莫队题就是 P5355 [Ynoi2017] 由乃的玉米田

P5355 [Ynoi2017] 由乃的玉米田

前三个用 bitset 配合莫队是简单的，但除法会出点问题，当 x≤Bx \leq B 的时候复杂度 O(nx)O(\frac n x) 有些吃不消。
但这些 xx 只有 BB 个，考虑单独处理。
离线对每个 xx 做一遍扫描线，对每个 rr 求最早的一个 ll ，满足 l,rl, r 中存在 a,ba, b 有 ba=x\frac b a = x ，扫的时候拿个桶对每个 bb 存最晚的一个 ax=bax = b ，记录答案只需要判断 mir≥lmi_r \ge l 就行 , mimi 是每个 rr 最晚的合法的 ll ，单次复杂度是 O(n+V)O(n+V) 的，做 BB 次完全不会超时限。
扣掉莫队的简单题和莫队与根号分治配合的题，还有一大类题就是序列分块。
先从小的讲起。

P5356 [Ynoi2017] 由乃打扑克

区间加区间第 kk 大，直接做可以做到 nnlog⁡nn\sqrt n \log n ，分散层叠最低能优化到 nnlog⁡nn \sqrt {n \log n} （默认 n,qn,q 同阶）。
具体讲下直接分块的实现，首先查询是要二分，然后变成查区间小于等于 xx 的数的个数。
散块查是 O(B)O(B) 的，整块是 O(nBlog⁡B)O(\frac n B \log B) 的，乘上二分过后发现复杂度上天了。
其实散块可以提前归并到一起，而且每次查询归并只用做一次，这是 O(B)O(B) 的，然后每次二分的查询变成 log⁡B+nBlog⁡B\log B + \frac n B \log B ，然后 BB 取 nlog⁡n\sqrt n \log n 时平衡，总复杂度变成 nnlog⁡nn \sqrt n\log n

P3712 少女与战车

这个题直接先 dfs 序把树拍扁，只要你的实现没锅，套用上边的分块就能过，但因为至于很小所以还有别的阴间做法。
谈几个大分块的经典题。

P4117 [Ynoi2018] 五彩斑斓的世界

大分块入门题，考虑 >x>x 减去 xx 的性质。
记一个块最大值为 mxmx
对于一个块，假如 mx>2xmx > 2x 那么直接暴力，打个整体减 xx 的 tag，然后把实际值 <x<x 的加上 xx，复杂度是 O(x)O(x) 的，mxmx 变化量也是 xx
假如 mx≤2xmx \leq 2x ，我们先给整个块打个整体加 xx 的 tag ，然后把实际值 >x>x 的减去 xx，复杂度是 O(mx−x)O(mx-x) 的，mxmx 变化量也是 mx−xmx - x
而一个块的 mxmx 总变化量是 VV 于是复杂度 O(VnB)O(\frac {Vn} B) ，空间也是相同的，所以考虑离线滚块将空间降到线性。

P4119 [Ynoi2018] 未来日记

区间将 xx 替换成 yy ，区间查第 kk 小。
区间第 kk 小的查询可以用序列分块配合值域分块完成。
替换还是考虑用并查集状的东西维护，不难发现一个块颜色数（数的种类数）是不断减少的，考虑替换的时候假如这个块含 xx 并且含 yy 直接暴力重构，这个最多做 O(B)O(B) 次，每次 O(B)O(B) ，然后假如含 xx 并且不含 yy ，把 xx 用并查集替换到 yy 上去。
主要难度在实现。

P7710 [Ynoi2077] stdmxeypz

小弱智题，先 dfs 序拍扁树，然后根号分治模数 aa ，用不同的分块维护就行了，空间随便卡卡就过了，乱取块长都能过。
所以为啥能有黑？

P7446 [Ynoi2007] rfplca

弹飞绵羊的强化版。
考虑同样的方式维护，对每个块维护两个数组 f,gf,g ，分别是跳出当前块以及在块内跳。
考虑每次修改暴力重构一下，经过 BB 次重构过后不难发现当前块里边的数一次就能跳出当前块，于是直接维护块内加的 tag 就行了。
求 lca 的过程类似树剖，慢慢跳，不难发现出块次数是 O(B)O(B) 的，所以复杂度是对的。

P4690 [Ynoi2016] 镜中的昆虫

区间覆盖区间数颜色。
Trick 题，考虑对每个数维护数组 fif_i 为下一个与它相等的数的位置。
不难发现 ff 的修改也是 O(n+q)O(n+q) 的级别的。
不难发现查询变成 ∑i=lr[fi>r]\sum_{i=l}^r\limits [f_i>r] 是个二维偏序的形式，于是用个序列分块套 O(B)O(B) 修，O(1)O(1) 查的值域分块。用 cdq 也可以。
为了卡空考虑离线滚块，常数很小轻松过。

P5397 [Ynoi2018] 天降之物

卡常题，全局做法是根号分治，分类讨论出现次数 >B>B 的以及 ≤B\leq B 的数，然后查询。
但是此题有序列分块做法，具体是维护块内答案，以及数的出现位置，然后从左往右扫。
块内只有 BB 个数，所以块内答案重新编号后是 O(B2)O(B^2) 的。
而一次单点修也只会改变一种数与其他数的答案，不难发现只会修改 BB 个值。
然后就完了。势能一下发现可以支持把区间的 xx 修改成 yy ，这就是手牵手走向明天那个题，然而和牛客模拟赛撞题了（我们考CSP模拟赛竟然考了这场）
简单的东西差不多就这些了。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...