@yijan https://www.luogu.org/blog/yihan/zhuang-ya-dp

感谢投稿，已经加入候选队列

@守望 https://www.luogu.org/blog/user9012/post-2-sat-lve-xie

感谢投稿，已经加入候选队列

本次审稿截止： 2018-8-15 23:00

今天真休闲

https://www.luogu.org/blog/codesonic/Mosalgorithm

莫队算法

@codesonic 不是在群里吼莫队怎么证明吗>w<

@yijan 窝假装我证出来了（逃

其实是假设n，m同阶然后就能证

@codesonic 复杂度分析不明确，怎么能假设n,m同阶呢？奇偶排序能快的原因是指针移到右边不用再次跳回左边往右边移动，减少一半操作

@codesonic qwq666%%%

@ComeIntoPower nm一般同阶啊

而且目前市面说法主要是是n根号n和n根号m的说法，证明也似乎都是对的，甚至有O（(N+M)*√N）的说法，但是证明似乎有疏漏窝看不懂。。。

我这里听从n根号n的证明

csdn里的博客似乎都是n根号n

修改完毕

https://www.luogu.org/blog/codesonic/Mosalgorithm

@codesonic 您拿您的带修改莫队去a一下P3939数颜色？我的跑TLE了（分块没分好。。）

@yijan 那题好像卡莫队。。。?

3e5莫队写个鬼啊

@codesonic 正确的方法不应该是令块大小为$S$，然后来分析复杂度吗，大概是$O(MS+N^2/S)$，因为每个询问最多移动$O(S)$，每个块最多移动$O(N)$，所以$S=N/\sqrt{M}$最优，此时复杂度为$O(N\sqrt{M})$； 更精确的算，复杂度应为$O(MS+N-S+N-2S+....+N-(N/S)*S)$ $=O(MS+N^2/S-(N+S)N/S/2)$ $=O(1/2*N^2/S+MS)$

所以当$MS=1/2*N^2/S$的时候，即$S=N/ \sqrt{M*2}$时候有最小复杂度（我也不知道算对没）当然块大小是要看情况调整的；带修莫队同理吧