当前位置：首页 > news >正文

Ynoi做题记录

news 2025/10/31 1:30:34

1.P5355 [Ynoi Easy Round 2017] 由乃的玉米田

标签：莫队，bitset，根号分治。

用 bitset 作为一个桶维护当前区间出现了多少个，因为值域不超过 $10^5$。

假设新出现一个数 $p$，那么就在 bitset 的 $now1$ 的位置 $p$ 设成 1、$now2$ 的位置 $10^5-p$ 设成 1。如果要去掉一个就改成 0。

令 $N=10^5$，对每一种操作分类讨论：

假设需要找的数是 $y,z$，需要满足 $z-y=x$，反过来就是 $z=x+y$。因此把 $now1$ 中的信息全部右移 $x$ 位与 $now1$ 比较是否有交集。
还是 $y,z$，需要满足 $z+y=x$。令 $y = N-y'$，那么 $z + N - y' = x$，即 $z - y' = -N + x$。这样就和情况一相同，看 $now2$ 左移 $N-x$ 与 $now1$ 是否有交集即可。
可以直接枚举 $x$ 的约数，在 $now1$ 看是否存在即可。
考虑根号分治：

对于 $x > \sqrt N $ 的情况，我们可以枚举 $\frac{y}{z}=x$ 中的 $z$，看 $zx$ 是否存在即可。最多只需要枚举 $\sqrt N$ 次。
对于 $x \le \sqrt N$ 的情况，可以把这些询问不放在莫队中离线，而是单独离线，枚举每一个 $i \le \sqrt N$，然后从前往后遍历序列，每一个位置 $j$ 记录自己即自己前面可以使得 $\frac{a_t}{a_j}=i$ 或 $a_t \times a_j = i$ 的最大一个 $t$，然后记录目前每一个前缀序列中最大的 $t$。就可以在总共 $n \sqrt N$ 的时间复杂度下完成所有这些询问。

时间复杂度 $O(n(\sqrt m + \frac{N}{w}) + n \sqrt N)$。

标签：莫队，bitset，离散化。

假设一个询问得到的三个可重集合是 $A_1,A_2,A_3$，那么答案就是 $|A_1|+|A_2|+|A_3|-3|A_1 \cap A_2 \cap A_3|$。因此对于一个询问可以拆成三个子询问扔进莫队中。

令 $N=10^5$。

集合维护因为需要取交集，所以理所当然用 bitset。但是最多有 $N$ 个数，每个数最多出现 $10^5$ 次，显然不能开 $N \times N$ 的 bitset 维护。但是这些数最多一共才出现 $N$ 次，所以只需要离散化后压位存进 bitset 中。

对于每个大询问也需要开 bitset 维护集合，但这样也是 $N \times N$ 的空间。因此可以把这些询问分成 5 次即可。

时间复杂度 $O(n(\sqrt m + \frac{N}{w}))$。

标签：分块，根号分治。

先把原序列分块。

考虑修改：

若 $x > \sqrt n$，就直接暴力跳进行修改，最多跳 $\sqrt n$ 次。
若 $x \le \sqrt n$，注意到 $y \le x$，那么整个序列中所有的位置在 $x$ 确定时都可以唯一确定 $y$ 的位置。也就是说在 $y$ 不同而 $x$ 相同时，每个修改操作 $(x,y)$ 影响的位置没有交集，且这些并集就是原序列。所以可以维护 $k=x$ 时对于 $y$ 位置的前缀和、后缀和，不修改原序列和大块。复杂度也是 $\sqrt n$ 的。（注意这里不能树状数组，因为后面查询需要 $O(1)$ 查询）。