No.1270 Range Arrange Query
stoq
tsutajNote
The execution time limit for this problem is 7s.
Also, using a fast language is recommended. (AC has been confirmed in C++ and Java.)
Problem Statement
You are given a sequence $A = \{a_i\}$ of length $N$.
Answer $Q$ queries. Each query is given in the following format.
-
$l \ r$
- Find the minimum inversion number of $A$ when changing $a_l,a_{l+1},\dots,a_r$ to any integers between $1$ and $N$, inclusive.
- Each element may be changed to a different value; they do not all need to be the same value. An element may also keep the same value as before the change.
The inversion number of $A$ is the number of pairs $(i,j) \ (1 \leq i < j \leq N)$ satisfying $a_i > a_j$. Note that the queries are independent, and the modified sequence is restored to the original each time.
Input
$N\ Q$ $a_1 \dots a_N$ $l_1 \ r_1$ $\vdots$ $l_Q \ r_Q$
- All inputs are integers.
- $1 \leq N,Q \leq 2 \times 10^4$
- $1 \leq a_i \leq N$
- $1 \leq l_i \leq r_i \leq N$
Output
On the $i$-th line, output the answer to the $i$-th query.
Sample
Sample 1
Input
5 3 3 1 1 4 2 2 3 5 5 1 5
Output
4 2 0
In the first query, for example, setting $a_2 = 2, \ a_3 = 3$ makes the inversion number 4, which is the minimum.
In the second query, for example, setting $a_5 = 5$ makes the inversion number 2, which is the minimum.
In the third query, for example, setting $a_1 = a_2 = \cdots = a_5 = 1$ makes the inversion number 0, which is the minimum.
Sample 2
Input
4 4 4 3 2 1 1 1 2 2 3 3 4 4
Output
3 4 4 3
Sample 3
Input
10 10 9 7 7 10 9 8 1 3 2 9 5 6 3 9 3 10 2 5 8 9 6 8 1 2 2 4 10 10 2 7
Output
24 1 1 12 15 15 17 15 25 9
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。