自动搬运

查看原文

来自洛谷，原作者为

	fjzzq2002 **

搬运于2025-08-24 21:52:46，当前版本为作者最后更新于2017-05-30 21:50:57，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

不妨从小到大枚举x，考虑计数j=x的情况。

当j=x时，我们可以发现不同的gcd和or只有$O(log)$种，因为你考虑从右到左枚举左端点，每次使用一个新元素更新gcd和or，那么gcd如果改变，必然少了至少一个质因子，or如果改变，必然至少多了二进制下一个1。质因子和二进制下最多1的个数都是log级别的，所以只有$O(log)$种。

如果你每次二分一下当前(gcd,or)这一段的左端点，那么是$O(log^2\times gcd)$的，理论上可以获得60分（实际上由于数据造的还是不够强，卡卡常好像能过）。

事实上我们发现从小到大枚举右端点的时候，我们可以直接把之前的log段并上当前这个新元素来更新每一段，这样就可以去掉一个log，是$O(log\times gcd)$的。事实上可以证明这是$O(log)$的。