关于分块的块大小
扯淡
以前都是O(sqrt(n))的块。然后现在面临被卡常的风险。
本来1e5的数据应该是支持O(nsqrt(n))=O(nlog^2n)的。
但是由于分块这个常数有点危险，所以我们还是要考虑考虑。尤其是在分块还要带log的情况下，就不得不警惕了。
分析
可以类似莫队复杂度分析得到。
假设我们的块的大小是Threshold，块的个数是Num。Num*Threshold=n。
根据双勾函数的性质，令此函数最小。此时：
即：
Threshold=sqrt(0.5*n*T(block)/T(sca))
复杂度为
O(sqrt(2*n*T(block)*T(sca)))
与Threshold=sqrt(n)的区别。
区别是很明显的。
我们用常用到的，T(block)=logn来计算。
那么合理分块的复杂度是从O(sqrt(n)logn)变为了O(sqrt(nlogn))。那么就是把17变为了4。这样使得分块的速度大大提高。
对于T(block)=T(sca)的思考
发现这样一来完全没有任何的优化。不能通过调整块的大小来加速。于是这样就是妥妥的O(sqrt(n)logn)了。
那么就需要优化算法，除非数据范围小。
对于纯暴力的思考
如果T(block)=O(Threshold)呢？那么这是一个纯暴力。
自然并不是上面看上去的O(sqrt(nsqrt(n)))。
显然是O(n)的。于是这样就退化了。
可见并不是T(block)与T(sca)相差越大越好。