捞一下对分治过程中关于 `size` 部分的问题的讨论

EndSaH @ 2019-08-21 11:32:53

by t162 @ 2019-08-21 11:34:05

Orz

by MagicDuck @ 2019-08-21 11:42:01

感觉点分治要凉了...

by MagicDuck @ 2019-08-21 11:43:15

看来以后还要写一个Get_size函数...

by Edward_Elric @ 2019-09-15 19:16:10

@EndSaH 请问大佬有没有好的解决办法了。

但是现在大家都是这么写的，到现在都没出问题？

by EndSaH @ 2019-09-15 20:45:40

@Edward_Elric 原贴里面有，每次额外求一遍 size 即可，复杂度还是对的，加了一点小常数而已。

by Edward_Elric @ 2019-09-15 21:33:01

@EndSaH 是的，但是如果我加这两倍的常数，说不定会被卡掉，因为这个算法的复杂度确实是很危险的。即使假算法没法保证复杂度。但是确实我没做到一道卡掉我这样写的题。所以我有点难抉择

by EndSaH @ 2019-09-15 22:08:29

@Edward_Elric emm 其实这不是两倍的常数，这个带来的常数影响微乎其微（相较于你计算的部分而言）。O(n \log^2n) 问题不大

by Edward_Elric @ 2019-09-16 08:43:08

@EndSaH 好像是的。。。