P9998 [Ynoi2000] rfrqwq

Alex_Wei · 2023-12-31 13:42:51 · 题解

P9998 [Ynoi2000] rfrqwq

看起来不能 \mathrm{polylog}。很多涉及集合操作的题目都不能 \mathrm{polylog}，本题是集合查询，所有颜色为 x 的位置构成集合。可根据 “集合” 通过 “根号” 构造出难以 \mathrm{polylog} 的情况：设 n = 2B(B + 1)，将序列分成 B 块，每块前 B + 1 个数分别为 1\sim B，其中第 i 块的 i 重复两次；后 B 个数任意。B 次修改，第 i 次任意修改第 i 块后 B 个数；接下来 B 次查询，第 i 次查询 (1, n, i)。非针对性算法难以优于 \mathcal{O}(B ^ 2)。

先算答案。将 x 视作 x，a_i \neq a_{i + 1} 的间隔视作 o，统计 xox 的个数。经典问题，维护五元组分别表示当前 x，o，xo，ox，xox 的个数。信息封闭，可快速合并，且具有结合律。

分块无非序列分块和时间轴分块（如果有别的分块方式恕笔者孤陋寡闻），两种都能做。考虑时间轴分块，每 B 个操作和询问为一块。2B 个端点将序列分成 2B + 1 块，操作只涉及整块。

扫一遍整个序列求出：

• 每一块的开头和结尾。

修改枚举每个块推平，更新每一块的开头和结尾。查询按顺序枚举每个块，如果当前块被推平，则贡献容易计算，否则利用预处理的 f。记得加上块间的贡献（记录开头和结尾的用处）。

时间复杂度 \mathcal{O}(n\sqrt n)，空间复杂度 \mathcal{O}(n)，其中 f 特别占空间，可对每个块离线处理做到 \mathcal{O}(B)。代码。

卡常：

• 直到总共有 2B 个端点再统一处理，需要限制查询的不同的 x 个数不超过某阈值，经试验设为 B 较合适。其中 B = 0.7\sqrt n。
• 在循环内开大小为 n 的 vector 会使申请空间消耗太多时间。