問題一覧 > 通常問題

No.3078 Difference Sum Query

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 52
作問者 : 👑 binap / テスター : nekoyukichi 👑 p-adic hamamu
2 ProblemId : 11990 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-03-27 23:32:00

問題文

$N$ 項の数列 $A=(A_1,A_2\cdots, A_N)$ が与えられます。 $Q$ 個のクエリを処理してください。

各クエリは L R X の形式で与えられます。

$$\sum_{i=L}^R |A_i - X|$$

を計算した結果を出力してください。

制約

  • $1\leq N \leq 10^5$

  • $1\leq A_i \leq 10^{10}$ $(1\leq i \leq N)$

  • $1\leq Q \leq 10^5$

  • $1\leq L \leq R \leq N$

  • $1\leq X \leq 10^{10}$

  • 入力は全て整数。

入力

$N$ $Q$
$A_1$ $A_2$ $\cdots$ $A_N$
$Query_1$
$Query_2$
$\vdots$
$Query_Q$

各 $Query_i$ は以下の形式で入力されます。

$L$ $R$ $X$

出力

$Q$ 行にわたって出力してください。 $i$ $(1\leq i \leq Q)$ 行目には $Query_i$ についての答えを整数で $1$ 行に出力してください。

サンプル

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

・ $1$ つ目のクエリの答えは $\displaystyle \sum_{i=1}^3 |A_i - 3| = |0| + |-2| + |1| = 3$ となります。

・ $2$ つ目のクエリの答えは $\displaystyle \sum_{i=3}^4 |A_i - 7| = |-3| + |-6| = 9$ となります。

サンプル2
入力
7 8
9 6 5 9 3 1 10
1 4 3
2 5 4
3 5 9
3 4 1
1 2 2
1 7 6
4 6 3
4 4 2
出力
17
9
10
12
11
19
8
7

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