为什么块的个数是M*logN

P4168 [Violet] 蒲公英

LRL52 @ 2019-05-24 11:20:26

lyd书上的第二种做法复杂度O(NT+MN/T*logN)，设把长度为n的区间分成T块但是通过均值不等式，当NT=MN/T*logN时有最小值嘛，此时T=\sqrt{M*logN}，但书上和题解却是T=\sqrt{N*logN}，为什么呢？？而且这样就不超时，改成T=\sqrt{M*logN}就超时了

by WAutomaton @ 2019-05-24 12:59:15

@LRL52 事实上本题有O((N+M)\sqrt N)的简单解法，把lyd讲的方法1用前缀和优化就好了。建议看看题解

by WAutomaton @ 2019-05-24 13:06:27

至于你说的问题，可能和常数不同有关

by 142857cs @ 2019-05-24 13:15:52

你是不是把块个数和块大小搞混了啊？

by 142857cs @ 2019-05-24 13:17:43

事实上本题有O((n+m)\sqrt n),空间O(n)的解法，详见http://olddrivertree.blog.uoj.ac/blog/4656

by 142857cs @ 2019-05-24 13:17:58

@LRL52

by LRL52 @ 2019-05-24 15:17:15

@142857cs @WAutomaton 感谢，问题已解决，只要加一句

if(n % tt) ++len;

就可以了，原因是因为我发现最后一个块的大小比较大，而数据r很多都接近n，所以卡我的复杂度。