区间逆序对的 O(nlog n)-O(1) 做法
OldDriverTree
·
·
休闲·娱乐
令 pre_x 为 [1,x] 的逆序对个数，suf_x 为 [x,n] 的逆序对个数，这显然能 O(n\log n) 求出。
对于一次询问 [l,r]，下面为了方便书写，用 x 表示 [l,r] 的数，y 表示 [1,l-1] 的数，z 表示 [r+1,n] 的数。
减掉 $pre_{l-1}+suf_{r+1}$，得到 $2x^2+xy+xz$。
接下来只需减掉 $x(x+y+z)$，即 $[l,r]$ 到全局的答案。
令 $a_x=pre_x-pre_{x-1}+suf_x-suf_{x+1}$，即为 $\sum\limits_{i=l}^r a_i$，可以预处理一下前缀和。
综上，我们把区间逆序对做到了 $O(n\log n)-O(1)$。
出处：由某学校模拟赛题解扩展而来（他们将区间互质对做到了 $O(n2^{\omega(V)})-O(1)$）。