单点时限: 1.0 sec
内存限制: 128 MB
$\texttt{sha7dow}$ 很喜欢根号复杂度的算法,在学习莫队二次离线时找到了区间逆序对的模板题。
给你一个长为 $\textit{n}$ 的序列 $\textit{a}$,$\textit{m}$ 次询问,每次查询一个区间的逆序对数。
$\textit{1} \leqslant \textit{n,m} \leqslant \textit{10}^{\textit{5}}$,$\textit{0} \leqslant \textit{a}_{\textit{i}} \leqslant \textit{10}^{\textit{9}}$。
$\texttt{sha7dow}$ 学习了整整一天才通过了这道模板题,所以他也想考考你,但没有数据的他打算用一种简单的方式生成所有查询的区间。
$\texttt{sha7dow}$ 发现这种生成方式似乎过于简单,所以对于每个区间 $S_i$,你还需要求出所有满足 $j_1<j_2$ 且 $j_1, j_2$ 奇偶性不同的 $T_{i,j_1}, T_{i,j_2}$ 拼接形成的序列的逆序对数之和。
第一行包含两个整数 $n,m$。
第二行包含 $n$ 个整数 $a_i$,表示给定的序列。
接下来 $m$ 行每行包含两个整数 $l_i,r_i$,表示第 $i$ 次查询的区间 $S_i = [l_i, r_i]$。保证查询的区间两两不同。
输出 $m$ 行,每行包含两个整数,分别表示区间 $S_i$ 的逆序对数和所有 $T_{i,j_1}, T_{i,j_2}$ 拼接形成的串的逆序对之和。
5 4 5 4 3 2 1 4 5 1 3 1 2 1 5
1 1 3 3 1 1 10 10
$1 \leqslant n,m \leqslant 10^5$
$0 \leqslant a_i \leqslant 10^9$
$1 \leqslant l_i \leqslant r_i \leqslant n$
序列 $a$ 的逆序对是失去自然次序的元素对,即满足 $i < j$ 且 $a_i > a_j$ 的有序对 $(i,j)$。