問題一覧 > 通常問題

No.2065 Sum of Min

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 105
作問者 : 遭難者遭難者 / テスター : 👑 p-adicp-adic ygussanyygussany とりゐとりゐ
3 ProblemId : 8066 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-02-04 15:41:07

問題文

$i=1,2,\ldots,Q$ に対し $\displaystyle\sum_{k=L_i}^{R_i}\min(X_i,A_k)$ を求めてください。

入力

$N\ Q$
$A_1\ A_2 \ldots A_N$
$L_1\ R_1\ X_1$
$L_2\ R_2\ X_2$
$\vdots$
$L_Q\ R_Q\ X_Q$

  • $1\le N\le 10^5$
  • $1\le Q\le 10^5$
  • $1\le A_k\le 10^9\ (1\le k\le N)$
  • $1\le L_i\le R_i\le N\ (1\le i\le Q)$
  • $1\le X_i\le 10^9\ (1\le i\le Q)$
  • 入力は全て整数である。

    • 出力

    $Q$ 行出力してください。
    $i$ 行目 $(1\le i\le Q)$ には $\displaystyle\sum_{k=L_i}^{R_i}\min(X_i,A_k)$ の値を出力してください。

    サンプル

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

    $\displaystyle\sum_{k=1}^3\min(5,A_k)=1+2+4=7$ です。したがって、 $1$ 行目には $7$ を出力してください。
    $\displaystyle\sum_{k=2}^3\min(3,A_k)=2+3=5$ です。したがって、 $2$ 行目には $5$ を出力してください。
    $\displaystyle\sum_{k=1}^3\min(1,A_k)=1+1+1=3$ です。したがって、 $3$ 行目には $3$ を出力してください。

    サンプル2
    入力
    5 1
1000000000 1000000000 1000000000 1000000000 1000000000
1 5 1000000000
    出力
    5000000000

    出力が32bit整数型に収まらない場合があることに注意してください。

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