自动搬运

查看原文

来自洛谷，原作者为

	zzx0102 原 sto_5k_orz || AFO on 2023.10.21

搬运于2025-08-24 22:47:26，当前版本为作者最后更新于2023-09-19 21:57:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P9335 [Ynoi2001] 雪に咲く花

神题，太神了。

考虑扫描线。

考虑当 $r$ 变大时，答案的变化量。

那么与，或，$\gcd$ 的每个值都只会最多修 $\log w$ 次，$w$ 为值域。

查询是 $\mathcal{O}(1)$ 的，总复杂度 $\mathcal{O}(n\log v)$。

上述都是废话，关键在于卡常。

首先，离线下来的扫描线不要用 vector 存储，自己胡个链式前向星。

然后读入用 fread，输出用 fwrite。

还有 $\gcd$ 用更相减损术。

$$\gcd(a,b) = \left \{ \begin{aligned} &\gcd(b,a-b)\ && a\bmod 2=1\ b\bmod 2=1 \\ &\gcd(\dfrac{a}{2},b)\ && a\bmod 2=0\ b\bmod 2=1 \\ &\gcd(a,\dfrac{b}{2})\ && a\bmod 2=1\ b\bmod 2=0 \\ &\gcd(\dfrac{a}{2},\dfrac{b}{2})\times 2\ && a\bmod 2=0\ b\bmod 2=0 \\ \end{aligned} \right. $$

虽然也是 $\mathcal{O}(\log a)$ 的，但是常数明显减小，近似 $\mathcal{O}(1)$。

然后尽量写主函数里面，函数调用会消耗时间。

CODE

弱化版 P8421。