No.924 紲星

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 23
作問者 : Lemma299Lemma299 / テスター : lumc_lumc_
1 ProblemId : 3124 / 出題時の順位表

数式が表示されない不具合が発生している場合は次の対応をお願いします.

https://twitter.com/yukicoder/status/1191757446596812800?s=20

問題文

長さ $N$ の整数列 $A$ が与えられます,数列 $A$ の $i$ 番目の値は $A_i$ です.
以下の形式のクエリが $Q$ 個与えられるので,処理してください.

  • $i$ 番目のクエリでは整数の組 $L_i, R_i$ が与えられるので,以下の関数 $f$ の最小値を求めてください.
    • $\displaystyle f(x) = \sum_{k = L_i}^{R_i} |x - A_k|$

[注意] この問題では正しい解法だとしても,Python などの低速な言語では TLE になる可能性があります[ごめんなさい]

入力

$N\ Q$
$A_1\ A_2\ \cdots\ A_{N - 1}\ A_N$
$L_1\ R_1$
$\vdots$
$L_Q\ R_Q$
  • $1 \le N, Q \le 2 \times 10^5$
  • $-10^9 \le A_i \le 10^9$
  • $1 \le L_i \le R_i \le N$
  • 入力はすべて整数.

出力

$Q$ 行出力し $i$ 行目にはクエリ $i$ の答えを整数で一行に出力してください.

なお最小値が必ず整数であることが証明出来ます.

サンプル

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

クエリ $1$ では $f(x) = |x-1| + |x-2| + |x-3| + |x-4| + |x-5|$ です.$x = 3$ のとき最小値 $f(x) = 6$ を達成します.

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

サンプル3
入力
20 10
-574 627 212 956 -285 161 -331 -107 -229 -87 -414 -917 842 835 566 117 -298 -608 -964 -182
2 10
9 10
11 12
4 12
19 19
6 17
14 15
1 13
5 13
16 20
出力
2908
142
503
2870
0
4730
269
5461
2756
1507

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。