[省选联考 2025] 追忆 题解

前言

最近突然想起来了，写给自己看的。

更可爱的阅读体验

思路

性质 A，52 pts

其实跟正解关系不大，但我比赛的时候会的是这个。

只修改 $a$，不修改 $b$。首先将所有点按 $b$ 重标号方便后续讨论。大力对 $a$ 分块，设块长为 $B$。对每个块处理 $f_S=\max\limits_{u\in S}\{a_u\}$，修改的时候直接对单块暴力重构，查询的时候整块用手写 bitset 查询点 $u$ 在每块所属的区间内的可达性集合，散块暴力枚举，总复杂度 $\mathcal{O}(q2^B+\frac{nq}{B}+qB)$，取 $B=12$ 时平衡。

100 pts

定期重构。设重构周期为 $B$。对于在上次重构后有修改的点，查询时暴力枚举判断是否满足条件。这部分复杂度 $\mathcal{O}(qB)$。依旧对 $a$ 分块，每次重构预处理对每个点 $u$ 和每个块 $i$ 预处理块中能被 $u$ 到达的点的 $b_v$ 最大值。如果块长是 $B'$，单次复杂度就是 $\mathcal{O}(\frac{mn}{B'})$。查询时依旧正常扫描整块和散块。那么总复杂度为 $\mathcal{O}(qB)+\mathcal{O}(\frac{mnq}{BB'}+qB')$，解得 $B=B'=(nm)^{\frac{1}{3}}$，$q,n,m$ 同阶时总复杂度 $\mathcal{O}(n^{\frac{5}{3}})$。

---

解答と称するものなくても

即使没有称得上是答案的什么

何かに訊ねてみよう

也向着某物去询问吧

夢やがて覚めて熱も冷める

梦终将醒来那份感情也会消却

靄が晴れ渡るのでしょう

迷雾终将会散去吧

夜ふたたび迴ってきてね

夜晚会再度到来吧

今太陽が沈んでゆく

现在太阳正在下沉

揺らいでる崩れそうな胡蝶の夢

摇曳着快要破碎的，胡蝶一梦

「焼き跡には夏草が」

「在烧尽的痕迹上，夏草生长」