RT,事情是这样的:
今天早上讨论区里一位老哥给出了内存访问不连续莫队卡过的实现。
下午一位初学莫队的同学开始拿这题练手普通莫队,并且按照预期地得到了 60 分。
我们告诉他,这道题数据被加强到 10610^6106 了,一般的莫队是过不了的。
然后机房一位魔幻老哥:“啊?莫队能过啊。”
我们:“你现在再交一遍试试。”
魔幻老哥:“我试试。”
然后,不开 O2 过了。提交记录
理论复杂度确实是 O(nn)O(n\sqrt n)O(nn)。
这么看来,该继续加强数据了。