洛谷 P5047
设 \(n, m\) 同阶。
题目中提到了 \(n^{1.5}\) 这个复杂度，虽然有神秘的 \(n^{\sqrt 2}\) 做法，但是 \(n\sqrt n\) 也足以通过（即使只有 \(250ms\)）
考虑有什么根号算法？那就莫队吧。（其实莫队属于一种分块）
考虑从 \([l, r - 1]\) 挪动到 \([l, r]\)，其实变化量就是 \(a_{l \sim r - 1}\) 中大于 \(a_r\) 的数量，用树状数组可以随便搞出 \(O(n \sqrt n \log n)\) 的做法，和暴力一样
如何优化呢？注意到这个是可以差分的，所以考虑二次离线莫队。令 \(f(x, l, r)\) 表示 \(a_{l \sim r}\) 中大于 \(a_r\) 的数量，那么 \(f(x, l, r) = f(x, 1, r) - f(x, l - 1)\)。令 \(F(x, r) = f(1, l, r)\)，那么变化量就是 \(f(r, l, r - 1) = F(r, r - 1) - F(r, l - 1)\)。
\(F(r, r - 1)\) 是好算的，主要是 \(F(r, l - 1)\)。根据二次离线的套路，考虑扫描线。从 \(1\) 扫到 \(l - 1\)，维护每个 \(r\) 的答案。
问题转化为了 \(O(n)\) 次区间加，\(O(n \sqrt n)\) 单点查。为了平衡复杂度，需要使用值域分块（树状数组两种都是 \(O(\log n)\)）。即对 \(O(\frac{n}{B})\)整块的整块打上标记，散块暴力加，查询时把两种标记加起来即可。这样就可以做到修改 \(O(\sqrt n)\)，查询 \(O(1)\)。
为了把查询的 \(r\) 存下来，可以发现 \(r\) 其实是一端区间，直接开个 vector 记录区间做右端点即可，这样将空间降为 \(O(n)\)。
\(F(r, r - 1)\) 也是可以一并算的。对于左端点移动将 \(f\) 中的“大于”换为“小于”即可。
时间复杂度：\(O(n \sqrt n)\)。
总结：想要搞出一个 \(O(n \log n)\) 的做法比较困难，结合题目提示可以想到莫队。不难搞出一个带 \(\log\) 做法，通过二次离线配合值域分块去掉 \(\log\)。