問題一覧 > 通常問題

No.1000 Point Add and Array Add

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 216
作問者 : tempura_pp / テスター : tsutaj
お気に入りにしたユーザー ProblemId : 3979 / 自分の提出
問題文最終更新日: 2020-02-28 06:37:22
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
yukicoder contest 239 (順位表) の他の問題:

Problem Statement

There are sequences $A$ and $B$ of length $N$. $A$ is a sequence given in the input, and $B$ is a sequence whose elements are all initially $0$.
A total of $Q$ queries of the following $2$ types are given. Find the sequence $B$ after processing all of them in order.

  • A $x$ $y$ : Add $y$ to $A_x$.
  • B $x$ $y$ : For each integer $i$ satisfying $x\leq i\leq y$, add $A_i$ to $B_i$.

Input

$N\ Q$
$A_1\ A_2\ \cdots \ A_N$
$c_1\ x_1\ y_1$
$c_2\ x_2\ y_2$
$\vdots$
$c_Q\ x_Q\ y_Q$

  • All given numbers are integers.
  • $1\leq N, Q\leq 200000$
  • $1\leq A_i \leq 10^9$
  • $c_i$ is either 'A' or 'B'.
    • If $c_i$ is 'A', then $1\leq x_i \leq N$, $1\leq y_i \leq 100000$.
    • If $c_i$ is 'B', then $1\leq x_i \leq y_i \leq N$.

Output

Output the elements of the sequence $B$ after processing all queries, in order, separated by spaces. Print a newline at the end.

Sample

Sample 1
Input
7 3
9 8 1 9 6 10 8
B 2 5
A 7 9
B 4 7
Output
0 8 1 18 12 10 17

  • The $1$st query makes $B$ equal to ${0, 8, 1, 9, 6, 0, 0}$.
  • The $2$nd query makes $A$ equal to ${9, 8, 1, 9, 6, 10, 17}$.
  • The $3$rd query makes $B$ equal to ${0, 8, 1, 18, 12, 10, 17}$.

Sample 2
Input
10 10
1 4 1 5 9 2 6 5 3 5
A 2 7
A 5 9
B 1 4
B 6 10
A 10 3
B 1 2
A 8 3
B 4 9
A 6 2
B 1 10
Output
3 33 2 15 36 8 18 21 9 13

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