@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}$时候有最小复杂度（我也不知道算对没）当然块大小是要看情况调整的；带修莫队同理吧