問題一覧 > 通常問題

No.3078 Difference Sum Query

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 62
作問者 : 👑 binap / テスター : nekoyukichi 👑 p-adic 👑 hamamu
お気に入りにしたユーザー ProblemId : 11990 / 自分の提出
問題文最終更新日: 2025-03-27 23:32:00
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 462 (順位表) の他の問題:

Problem Statement

You are given a sequence $A=(A_1,A_2\cdots, A_N)$ of $N$ terms. Process $Q$ queries.

Each query is given in the form L R X.

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

Compute the above and output the result.

Constraints

  • $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}$

  • All inputs are integers.

Input

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

Each $Query_i$ is given in the following format.

$L$ $R$ $X$

Output

Output $Q$ lines. On the $i$-th line $(1\leq i \leq Q)$, output the answer to $Query_i$ as an integer on $1$ line.

Sample

Sample 1
Input
4 2
3 1 4 1
1 3 3
3 4 7
Output
3
9

・The answer to the $1$st query is $\displaystyle \sum_{i=1}^3 |A_i - 3| = |0| + |-2| + |1| = 3$.

・The answer to the $2$nd query is $\displaystyle \sum_{i=3}^4 |A_i - 7| = |-3| + |-6| = 9$.

Sample 2
Input
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
Output
17
9
10
12
11
19
8
7

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