Ynoi Easy Round 2024-526互联

下午要回校准备月考，限时复活一会找找存在感。都是口胡。

gcd 这个东西的经典结论是变 log 次就会变成 1。所以又是势能线段树。记一下 LCM 即可。注意到 LCM 如果非常大就不可能满足条件，所以 LCM 和 1e18 不断 check min 即可。

离线询问所以可以扫描线。然后等价于区间 01 翻转，历史和线段树。

一定有一个数没有出现，还是扫描线，强制最右端的那个数没有出现，然后贡献是前后缀 check max，树状数组可以小常数单 log 通过。

这个贡献等价于算子树内邻域深度和。dsu 或者主席树在线询问都是可以的。参考 critnos 的树链剖分日报。

幻视 seg-beats，但是 \(<x\) 的限制不允许我们这样做。于是考虑分块。

分块完发现块内排序，询问二分即可。块内排序的部分可以换成归并，二分的 log 怎么去掉题解里有写但我没看懂。好像还可以分散层叠。

哎呀这不是我们洛谷 2022 秋令营的题吗，怎么又被 lxl 搬了一遍。

根号分治即可。小的暴力，大的存起来询问的时候算。BSGS + 预处理优化可以单根号，常数貌似不大。