题解 P3794 【签到题IV】

fjzzq2002 · 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)的。