8847: [yosupo] Data Structure - Static Range Inversions Query
[Creator : ]
Description
You are given an integer sequence $(A_0, A_1, \ldots, A_{N-1})$
with the length $N$. Process the following $Q$ queries in order.
- $l_i$ $r_i$: Print the number of inversions in $(A_{l_i}, A_{l_i+1}, \ldots, A_{r_i-1})$
An inversion in a sequence $(B_0, B_1, \ldots, B_{M-1})$
is a pair of indices $(i, j)$ such that
$0 \leq i < j \lt M$ and $B_i \gt B_j$.
with the length $N$. Process the following $Q$ queries in order.
- $l_i$ $r_i$: Print the number of inversions in $(A_{l_i}, A_{l_i+1}, \ldots, A_{r_i-1})$
An inversion in a sequence $(B_0, B_1, \ldots, B_{M-1})$
is a pair of indices $(i, j)$ such that
$0 \leq i < j \lt M$ and $B_i \gt B_j$.
Input
$N$ $Q$
$A_0$ $A_1$ $\ldots$ $A_{N-1}$
$l_0$ $r_0$
$l_1$ $r_1$
$\vdots$
$l_{Q-1}$ $r_{Q-1}$
$A_0$ $A_1$ $\ldots$ $A_{N-1}$
$l_0$ $r_0$
$l_1$ $r_1$
$\vdots$
$l_{Q-1}$ $r_{Q-1}$
Constraints
$1 \leq N \leq 100,000$
$1 \leq Q \leq 100,000$
$0 \leq A_i \leq 10^9$
$0 \leq l_i \lt r_i \leq N$
$1 \leq Q \leq 100,000$
$0 \leq A_i \leq 10^9$
$0 \leq l_i \lt r_i \leq N$
Sample 1 Input
4 2
4 1 4 0
1 3
0 4
Sample 1 Output
0
4