問題一覧 > 通常問題

No.3078 Difference Sum Query

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

問題文

NN 項の数列 A=(A1,A2⋯ ,AN)A=(A_1,A_2\cdots, A_N) が与えられます。 QQ 個のクエリを処理してください。

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

∑i=LR∣Ai−X∣\sum_{i=L}^R |A_i - X|

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

制約

  • 1≤N≤1051\leq N \leq 10^5

  • 1≤Ai≤10101\leq A_i \leq 10^{10} (1≤i≤N)(1\leq i \leq N)

  • 1≤Q≤1051\leq Q \leq 10^5

  • 1≤L≤R≤N1\leq L \leq R \leq N

  • 1≤X≤10101\leq X \leq 10^{10}

  • 入力は全て整数。

入力

NN QQ
A1A_1 A2A_2 ⋯\cdots ANA_N
Query1Query_1
Query2Query_2
⋮\vdots
QueryQQuery_Q

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

LL RR XX

出力

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

サンプル

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

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

・ 22 つ目のクエリの答えは ∑i=34∣Ai−7∣=∣−3∣+∣−6∣=9\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もしくは右上の雲マークをクリックしてアカウントを作成してください。