P9335 [Ynoi2001] 雪に咲く花 题解

· · 题解

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。