escape from whk 3题解

题目大意

定义两个不同质因数为kuhu，当且仅当两数和为2的整数次方.

1. 给定若干询问\([l,r]\)，问在区间中取出若干的元素，使得元素两两间不为kuhu，最大的元素个数\(f(l,r)\)
2. 求\(\sum_{1\le l\le r\le n}f(l,r)\)

题解

Part1

如图，对于一个右端点，找到一个最接近它的2的整数次方x

)

我们发现，对于\([x+1,r]\)和\([2x-r,x-1]\)两段只能选择一段，但\([x+1,r]\)的影响更小（因为选择了另一个会影响前面），所以就直接选择\([x,r]\)，然后就不能选择\([2x-r,x-1]\)，所以答案就是\(ask(l,r)=ask(l,2x-r-1)+r-x+1\)

我们发现这样递归，x每次都会变小，所以是\(\log n\)的单次查询，时间复杂度\(O(m\log n+num·n^2\log n)\)，可以获得75分

Part2

现在的问题就是如何处理第二问。

我们令\(s_r=\sum_{l=1}^rf(l,r)\)

考虑分类讨论：

1. \(l\in[x,r]\)，贡献为\(r-l\)，总贡献为\(\frac{(r-x+1)(r-x+2)}{2}\)
2. \(l\in[2x-r,x-1]\)，贡献为\(r-x+1\)
3. \(l\in[1,2x-r-1]\)，贡献为\(f(l,2x-r-1)+r-x+1\)

综合三种，可以得出递推式：\(s_r=\frac{(r-x+1)(r-x+2)}{2}+(x-1)(r-x+1)+s_{2x-r-1}\)

总时间复杂度为\(O(m\log n+n)\)，而且非常好打，并且爆标了。