問題一覧 > 通常問題

No.3330 Many Point Chmax Range Sum

レベル : / 実行時間制限 : 1ケース 3.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 3
作問者 : 👑 ArcAki / テスター : kidodesu
ProblemId : 12358 / 自分の提出
問題文最終更新日: 2025-10-31 20:20:52

注意

この問題は制限時間が厳しくPyPy3でのACは確認していません。C++相当の速度の言語をご利用ください。

問題文

長さ $N$ の数列 $A$ と $A$ に対する $K$ 個の操作が与えられます。
各操作の内容は以下のとおりです。ただし操作 $k$ とは $k$ 番目に与えられる操作のことを指します。

  • 操作 $k$
    • $1 ≤ p_k ≤ N$ なる正整数 $p_k$ 及び正整数 $X_k$が与えられる。$A_{p_k}$ を $\max(A_{p_k}, X_k)$ に変更する。
$Q$ 個のクエリが与えられ、それぞれ以下の内容となっています。
  • クエリ $j$
    • $1 ≤ L_j ≤ R_j ≤ K, 1 ≤ D_j ≤ U_j ≤ N$ なる正整数 $L_j, R_j, D_j, U_j$ が与えられる。
      $L_j ≤ k ≤ R_j$ なる各正整数 $k$ について昇順に操作 $k$ を行なった場合の、 更新後の $A$ における $\sum_{i=D_j}^{U_j}{A_i}$ の値を出力する。
      この操作は他のクエリには影響しない。
各質問クエリに答えてください。

入力

$N\ K\ Q$
$A_1$ $\ldots$ $A_N$
$Update_1$
$\vdots$
$Update_K$
$Query_1$
$\vdots$
$Query_Q$
ただし $Update_k$ は $k$ 番目の操作を表し以下の形式で与えられる。 
$p_k\ X_k$
また $Query_j$ は $j$ 番目のクエリを表し以下の形式で与えられる。 
$L_j\ R_j\ D_j\ U_j$

  • 入力はすべて整数で与えられる。
  • $1 ≤ N, K, Q ≤ 1.5 × 10^5$
  • $1 ≤ A_i ≤ 10^9$
  • 操作について以下を満たす。
    • $1 ≤ p_k ≤ N$
    • $1 ≤ X_k ≤ 10^9$
  • クエリについては以下を満たす。
    • $1 ≤ L_j ≤ R_j ≤ K$
    • $1 ≤ D_j ≤ U_j ≤ N$

出力

$Q$ 行出力してください。$j$ 行目ではクエリ $j$ の答えを出力し改行してください。

サンプル

サンプル1
入力
5 6 4
1 2 3 4 5
1 3
2 5
3 11
4 6
5 7
3 13
2 4 1 4
1 2 4 5
3 6 3 5
1 5 1 5
出力
23
9
26
32

例えば質問クエリ $1$ では操作 $2-4$ を昇順に適用したときの $A = [1, 5, 11, 6, 5]$ における $A[1:4]$ (閉区間表示) の総和を求めるので答えは $23$ です。
他のクエリでの操作ではAはそれぞれ順に以下のようになっています。

  • $[3, 5, 3, 4, 5]$
  • $[1, 2, 13, 6, 7]$
  • $[3, 5, 11, 6, 7]$

サンプル2
入力
8 15 10
15 18 16 1 9 8 5 20
3 42
5 39
4 33
4 23
6 9
5 5
3 50
8 47
1 30
4 7
3 48
7 26
8 19
6 13
2 43
13 15 1 8
4 6 4 8
2 4 2 7
1 2 6 7
5 11 2 5
10 13 6 6
8 10 2 7
11 11 8 8
1 15 2 5
3 15 1 6
出力
122
66
119
13
84
8
63
20
165
178

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