No.2333 Slime Structure
タグ : / 解いたユーザー数 33
作問者 :
hikikomori
sepa38
Problem Statement
Colored slimes are lined up in a row from left to right. From the left, there are $B_1$ slimes with attack power $A_1$, $B_2$ slimes with attack power $A_2$, ......, and $B_N$ slimes with attack power $A_N$.
Slimes can form a team consisting of $1$ or more consecutive slimes.
The overall power of a team is defined as the sum of the attack powers of the slimes in the team.
You are given $Q$ queries. Process each of them in order.
1 x y: Change the attack power of the $x$-th slime from the left to $y$.2 l r: When a team is formed among the $l$-th through $r$-th slimes from the left, output the maximum possible overall power of the team.
Constraints
- $2 \leq N \leq 10^5$
- $1 \leq Q \leq 10^5$
- $| A_i | \leq 10^5$
- $1 \leq B_i \leq 10^5$
- $1 \leq x \leq \sum_{i = 1}^{N} B_i$
- $| y | \leq 10^5$
- $1 \leq l \leq r \leq \sum_{i = 1}^{N} B_i$
- All input values are integers.
Input
The input is given from standard input in the following format.
$N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$ $Q$ query $1$ query $2$ $\vdots$ query $Q$
Each query is given in one of the following $2$ formats.
$1$ $x$ $y$
$2$ $l$ $r$
Output
Let $q$ be the number of queries of type $2$. Output $q$ lines.
On the $j$-th line $(1 \leq j \leq q)$, output the answer to the $j$-th such query.
Sample
Sample 1
Input
8 2 1 -7 2 3 2 -5 1 5 1 -3 2 7 2 -2 1 7 2 1 12 1 10 -2 2 1 12 2 1 10 1 7 10 2 1 10 2 2 3
Output
14 7 6 11 -7
Initially, the attack powers of the slimes are $(2, -7, -7, 3, 3, -5, 5, -3, -3, 7, 7, -2)$ from left to right.
For query $1$, an overall power of $14$ can be achieved by forming a team with the slimes at positions $10, 11$ from the left.
For query $2$, the attack powers of the slimes become $(2, -7, -7, 3, 3, -5, 5, -3, -3, -2, 7, -2)$ from left to right.
For query $4$, an overall power of $6$ can be achieved by forming a team with the slimes at positions $4, 5$ from the left.
For query $5$, the attack powers of the slimes become $(2, -7, -7, 3, 3, -5, 10, -3, -3, -2, 7, -2)$ from left to right.
For query $6$, an overall power of $11$ can be achieved by forming a team with the slimes at positions $4, 5, 6, 7$ from the left.
Note that a team of $0$ slimes cannot be formed.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。