[Ynoi2019 模拟赛] Yuno loves sqrt technology I

区间在线逆序对板子。

块内分别记录下排序后的结果，并对每个块分别预处理，块内所有前缀和后缀内逆序对个数，以及对于每个 $k\in[1,n]$，块中有多少大于等于 $k$ 的数。

这样就可以很方便求出 $f_{i,j}$ 表示有多少这样的逆序对，使得第一个数在前缀 $[1,j)$ 中，第二个数在块 $i$ 中；$g_{i,j}$ 表示有多少这样的逆序对，使得第一个数在块 $i$ 中，第二个数在后缀 $[j,n)$ 中。对于每个块我们只需要考虑与其不交的前/后缀即可。

然后我们将所有逆序对分为四种：

• 两个数在同一块内，$O(\frac nB)$ 对所有整块，以及两个散块的前后缀和求和得到；
• 第二个数在整块内，讨论第二个数在哪个整块，那么第一个数就被限制在一个区间内，将区间表示为两个前缀相减，通过 $f$ 求出；
• 第二个数在右端散块内，第一个数在整块内，讨论第一个数在哪个整块，第二个数就被限制在右端散块这个区间内，表示为两个后缀相减，通过 $g$ 求出；
• 第二个数在右端散块内，第一个数在左端散块内，对两端块排序过后的数组双指针统计。

如果询问的区间完全被包含在一个块内，考虑容斥，设块左端点为 $t$，用 $[t,r)$ 内的逆序对数减去 $[t,l)$ 内的逆序对数和左端点在 $[t,l)$ 且右端点在 $[l,r)$ 内的逆序对数集合即可，其中前两部分已经预处理过，第三部分可以对该块排序后的数组进行简单的统计。