E - Household Budget and Target Balance Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は、N 件の取引が順番に記録された家計簿を管理しています。i 番目の取引には種類 D_i と金額 B_i が書かれています。

  • 種類が R のとき、その金額を残高に加えます（入金）。
  • 種類が L のとき、その金額を残高から引きます（出金）。

高橋君は Q 個の操作を入力順に処理します。操作は以下の 2 種類です。

  • 1 p D b：p 番目の取引を、種類 D、金額 b に修正する。
  • 2 K：現在の家計簿について、残高を 0 として 1 番目から順に各取引を処理したとき、取引を処理した直後の残高が初めて K 以上になる取引の番号を答える。どの取引の処理後にも残高が K 以上にならない場合は 0 を答える。

ここで、i 番目の取引の番号は i です。残高は途中で負になることもあります。

タイプ 2 の操作は質問であり、家計簿の内容は変化しません。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 操作全体に含まれるタイプ 2 の操作の個数を M とすると、1 \leq M かつ N+Q+M \leq 2 \times 10^5
  • D_i \in \{\texttt{R}, \texttt{L}\}
  • 1 \leq B_i \leq 10^9
  • B_i は整数
  • タイプ 1 の操作について：
  • 1 \leq p \leq N
  • D \in \{\texttt{R}, \texttt{L}\}
  • 1 \leq b \leq 10^9
  • b は整数
  • タイプ 2 の操作について：
  • 1 \leq K \leq 2 \times 10^{14}
  • K は整数

入力

N Q
D_1 B_1
D_2 B_2
:
D_N B_N
\mathrm{Query}_1
\mathrm{Query}_2
:
\mathrm{Query}_Q
  • 1 行目には、取引の件数 N と操作の個数 Q が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目には、i 番目の取引の種類 D_i と金額 B_i が、スペース区切りで与えられる。
  • 続く Q 行には、操作が以下のいずれかの形式で与えられる。
1 p D b

2 K
  • 1 p D b は、p 番目の取引を種類 D（R または L）、金額 b に修正する操作を表す。
  • 2 K は、目標残高 K に対する質問を表す。

出力

タイプ 2 の操作ごとに、答えを 1 行に出力してください。

入力例 1

5 6
R 10
L 3
R 5
L 20
R 15
2 7
2 12
1 4 L 4
2 12
1 2 R 2
2 20

出力例 1

1
3
3
5

入力例 2

3 4
L 10
R 5
L 1
2 1
2 100
1 2 L 5
2 1

出力例 2

0
0
0

入力例 3

10 12
R 8
L 4
R 15
L 10
R 7
R 3
L 20
R 25
L 5
R 6
2 10
2 20
1 7 L 5
2 30
1 4 R 12
2 40
1 1 L 3
2 5
2 50
1 10 L 2
2 25
2 60

出力例 3

3
8
8
6
3
8
5
0

入力例 4

30 30
R 100
L 40
R 70
L 150
R 200
L 30
L 80
R 300
L 120
R 50
R 400
L 500
R 600
L 100
R 90
L 250
R 700
L 60
R 30
L 20
R 1000
L 800
R 450
L 300
R 200
L 100
R 50
L 400
R 900
L 700
2 100
2 500
1 4 R 150
2 500
1 12 L 100
2 1000
1 22 R 800
2 2000
1 28 R 400
2 2500
1 1 L 100
2 50
2 3000
1 17 L 700
2 1500
1 30 R 700
2 3500
1 7 R 80
2 1200
1 21 L 1000
2 1000
1 5 L 200
2 800
1 13 L 600
2 700
1 2 R 40
2 600
1 29 L 900
2 400
2 5000

出力例 4

1
11
8
11
21
21
4
22
22
29
13
13
13
30
11
11
0

入力例 5

1 1
R 1000000000
2 200000000000000

出力例 5

0

Score : 466 pts

Problem Statement

Takahashi manages a household budget book in which N transactions are recorded in order. The i-th transaction has a type D_i and an amount B_i.

  • If the type is R, the amount is added to the balance (deposit).
  • If the type is L, the amount is subtracted from the balance (withdrawal).

Takahashi processes Q operations in the order they are given. There are 2 types of operations:

  • 1 p D b: Modify the p-th transaction to have type D and amount b.
  • 2 K: For the current state of the budget book, starting with a balance of 0 and processing each transaction from the 1-st onward, answer the number of the first transaction after which the balance becomes at least K. If the balance never reaches K or more after any transaction, answer 0.

Here, the number of the i-th transaction is i. The balance may become negative during processing.

Type 2 operations are queries and do not change the contents of the budget book.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • Let M be the number of type 2 operations among all operations. Then 1 \leq M and N+Q+M \leq 2 \times 10^5.
  • D_i \in \{\texttt{R}, \texttt{L}\}
  • 1 \leq B_i \leq 10^9
  • B_i is an integer
  • For type 1 operations:
  • 1 \leq p \leq N
  • D \in \{\texttt{R}, \texttt{L}\}
  • 1 \leq b \leq 10^9
  • b is an integer
  • For type 2 operations:
  • 1 \leq K \leq 2 \times 10^{14}
  • K is an integer

Input

N Q
D_1 B_1
D_2 B_2
:
D_N B_N
\mathrm{Query}_1
\mathrm{Query}_2
:
\mathrm{Query}_Q
  • The first line contains the number of transactions N and the number of operations Q, separated by a space.
  • In the following N lines, the i-th line contains the type D_i and amount B_i of the i-th transaction, separated by a space.
  • The following Q lines each contain an operation in one of the following formats:
1 p D b

2 K
  • 1 p D b represents an operation that modifies the p-th transaction to type D (R or L) and amount b.
  • 2 K represents a query for the target balance K.

Output

For each type 2 operation, output the answer on a single line.

Sample Input 1

5 6
R 10
L 3
R 5
L 20
R 15
2 7
2 12
1 4 L 4
2 12
1 2 R 2
2 20

Sample Output 1

1
3
3
5

Sample Input 2

3 4
L 10
R 5
L 1
2 1
2 100
1 2 L 5
2 1

Sample Output 2

0
0
0

Sample Input 3

10 12
R 8
L 4
R 15
L 10
R 7
R 3
L 20
R 25
L 5
R 6
2 10
2 20
1 7 L 5
2 30
1 4 R 12
2 40
1 1 L 3
2 5
2 50
1 10 L 2
2 25
2 60

Sample Output 3

3
8
8
6
3
8
5
0

Sample Input 4

30 30
R 100
L 40
R 70
L 150
R 200
L 30
L 80
R 300
L 120
R 50
R 400
L 500
R 600
L 100
R 90
L 250
R 700
L 60
R 30
L 20
R 1000
L 800
R 450
L 300
R 200
L 100
R 50
L 400
R 900
L 700
2 100
2 500
1 4 R 150
2 500
1 12 L 100
2 1000
1 22 R 800
2 2000
1 28 R 400
2 2500
1 1 L 100
2 50
2 3000
1 17 L 700
2 1500
1 30 R 700
2 3500
1 7 R 80
2 1200
1 21 L 1000
2 1000
1 5 L 200
2 800
1 13 L 600
2 700
1 2 R 40
2 600
1 29 L 900
2 400
2 5000

Sample Output 4

1
11
8
11
21
21
4
22
22
29
13
13
13
30
11
11
0

Sample Input 5

1 1
R 1000000000
2 200000000000000

Sample Output 5

0