問題一覧 > 通常問題

No.2333 Slime Structure

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 33
作問者 : dyktr_06 / テスター : firiexp tyawanmusi hikikomori sepa38
お気に入りにしたユーザー ProblemId : 9596 / 自分の提出
問題文最終更新日: 2023-05-12 00:08:42
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
MMA Contest 015 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。