No.3330 Many Point Chmax Range Sum
問題文最終更新日: 2025-10-31 20:20:52
English (AI translation)
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)$.
-
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.
-
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.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
kidodesu