問題一覧 > 通常問題

No.1270 Range Arrange Query

レベル : / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 33
作問者 : 👑 stoqstoq / テスター : tsutajtsutaj
6 ProblemId : 5223 / 出題時の順位表
問題文最終更新日: 2020-10-23 21:05:41

注意

この問題の実行制限時間は7sです。
また、高速な言語の使用を推奨します。(C++及びJavaでのACを確認しています。)

問題文

長さ $N$ の数列 $A = \{a_i\}$ が与えられます。
$Q$ 個のクエリに答えてください。それぞれのクエリは以下の形式で与えられます。

  • $l \ r$
    • $a_l,a_{l+1},\dots,a_r$ を $1$ 以上 $N$ 以下の好きな整数に変更するときの $A$ の転倒数の最小値を求める。
    • 各要素は別々の値に変更でき、全て同じ値にする必要はありません。また、変更前と同じ値でも構いません。

$A$ の転倒数とは、$a_i > a_j$ を満たす $(i,j) \ (1 \leq i < j \leq N)$ の個数です。またそれぞれのクエリは独立しており、 変更した数列は毎回元に戻ることに注意してください。

入力

$N\ Q$
$a_1 \dots a_N$
$l_1 \ r_1$
$\vdots$
$l_Q \ r_Q$

  • 入力は全て整数
  • $1 \leq N,Q \leq 2 \times 10^4$
  • $1 \leq a_i \leq N$
  • $1 \leq l_i \leq r_i \leq N$

出力

$i$ 行目に $i$ 番目のクエリの解を出力してください。

サンプル

サンプル1
入力
5 3
3 1 1 4 2
2 3
5 5
1 5
出力
4
2
0

1番目のクエリでは、例えば $a_2 = 2, \ a_3 = 3$ とすると、転倒数は4となりこれが最小です。
2番目のクエリでは、例えば $a_5 = 5$ とすると、転倒数は2となりこれが最小です。
3番目のクエリでは、例えば $a_1 = a_2 = \cdots = a_5 = 1$ とすると、転倒数は0となりこれが最小です。

サンプル2
入力
4 4
4 3 2 1
1 1
2 2
3 3
4 4
出力
3
4
4
3

サンプル3
入力
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
出力
24
1
1
12
15
15
17
15
25
9

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。