問題一覧 > 通常問題

No.3330 Many Point Chmax Range Sum

レベル : / AI推定難易度 : 2325 / 実行時間制限 : 1ケース 3.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 4
作問者 : 👑 ArcAki / テスター : kidodesu
お気に入りにしたユーザー ProblemId : 12358 / 自分の提出
問題文最終更新日: 2025-10-31 20:20:52
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

Note

This problem has a strict time limit, and AC with PyPy3 has not been confirmed. Please use a language with speed comparable to C++.

Problem Statement

You are given a sequence $A$ of length $N$ and $K$ operations on $A$.
Each operation is as follows. Here, operation $k$ refers to the $k$-th given operation.

  • Operation $k$
    • A positive integer $p_k$ with $1 ≤ p_k ≤ N$ and a positive integer $X_k$ are given. Change $A_{p_k}$ to $\max(A_{p_k}, X_k)$.
$Q$ queries are given, each of which is as follows.
  • Query $j$
    • Positive integers $L_j, R_j, D_j, U_j$ with $1 ≤ L_j ≤ R_j ≤ K, 1 ≤ D_j ≤ U_j ≤ N$ are given.
      Suppose that operation $k$ is performed for each positive integer $k$ with $L_j ≤ k ≤ R_j$ in ascending order. Output the value of $\sum_{i=D_j}^{U_j}{A_i}$ for the updated $A$.
      These operations do not affect other queries.
Answer each query.

Input

$N\ K\ Q$
$A_1$ $\ldots$ $A_N$
$Update_1$
$\vdots$
$Update_K$
$Query_1$
$\vdots$
$Query_Q$
Here, $Update_k$ represents the $k$-th operation and is given in the following format.
$p_k\ X_k$
Also, $Query_j$ represents the $j$-th query and is given in the following format.
$L_j\ R_j\ D_j\ U_j$

  • All inputs are integers.
  • $1 ≤ N, K, Q ≤ 1.5 × 10^5$
  • $1 ≤ A_i ≤ 10^9$
  • The operations satisfy the following.
    • $1 ≤ p_k ≤ N$
    • $1 ≤ X_k ≤ 10^9$
  • The queries satisfy the following.
    • $1 ≤ L_j ≤ R_j ≤ K$
    • $1 ≤ D_j ≤ U_j ≤ N$

Output

Output $Q$ lines. On the $j$-th line, output the answer to query $j$, followed by a newline.

Sample

Sample 1
Input
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
Output
23
9
26
32

For example, in query $1$, we need the sum of $A[1:4]$ (as a closed interval) in $A = [1, 5, 11, 6, 5]$ obtained by applying operations $2-4$ in ascending order, so the answer is $23$.
For the other queries, A after the operations becomes the following, in order.

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

Sample 2
Input
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
Output
122
66
119
13
84
8
63
20
165
178

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