問題一覧 > 通常問題

No.2065 Sum of Min

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

問題文

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

入力

N QN\ Q
A1 A2…ANA_1\ A_2 \ldots A_N
L1 R1 X1L_1\ R_1\ X_1
L2 R2 X2L_2\ R_2\ X_2
⋮\vdots
LQ RQ XQL_Q\ R_Q\ X_Q

  • 1≤N≤1051\le N\le 10^5
  • 1≤Q≤1051\le Q\le 10^5
  • 1≤Ak≤109 (1≤k≤N)1\le A_k\le 10^9\ (1\le k\le N)
  • 1≤Li≤Ri≤N (1≤i≤Q)1\le L_i\le R_i\le N\ (1\le i\le Q)
  • 1≤Xi≤109 (1≤i≤Q)1\le X_i\le 10^9\ (1\le i\le Q)
  • 入力は全て整数である。

    • 出力

    QQ 行出力してください。
    ii 行目 (1≤i≤Q)(1\le i\le Q) には ∑k=LiRimin⁡(Xi,Ak)\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

    ∑k=13min⁡(5,Ak)=1+2+4=7\displaystyle\sum_{k=1}^3\min(5,A_k)=1+2+4=7 です。したがって、 11 行目には 77 を出力してください。
    ∑k=23min⁡(3,Ak)=2+3=5\displaystyle\sum_{k=2}^3\min(3,A_k)=2+3=5 です。したがって、 22 行目には 55 を出力してください。
    ∑k=13min⁡(1,Ak)=1+1+1=3\displaystyle\sum_{k=1}^3\min(1,A_k)=1+1+1=3 です。したがって、 33 行目には 33 を出力してください。

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

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

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