E - Dungeon Exploration Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君はダンジョンに挑みます。ダンジョンには N 個の部屋が一列に並んでおり、入口に近い方から順に部屋 1, 部屋 2, \ldots, 部屋 N と番号がついています。各部屋にはモンスターが 1 体ずついます。

高橋君がダンジョンに挑む際は、部屋 1 から順に部屋 2, 部屋 3, \ldots と一つずつ進み、各部屋で必ずモンスターと戦います。途中の部屋を飛ばすことはできません。部屋 i のモンスターを倒すには、戦闘前の時点で戦闘力が A_i 以上必要です。モンスターを倒すと、戦闘力が B_i 増加します。モンスターを倒せなかった場合、高橋君はそこで探索を終了します。すべてのモンスターを倒した場合も探索は終了します。

Q 個のイベントが順に与えられます。イベントには次の 2 種類があります。

  • 1 i a b：部屋 i のモンスターの情報が更新され、以後、倒すために必要な戦闘力が a に、倒したときに増加する戦闘力が b に変わります。
  • 2 s：高橋君が初期戦闘力 s で部屋 1 からダンジョンに挑みます。その時点での部屋の情報に基づいて、高橋君が倒すことができるモンスターの数を求めてください。

種類 2 の各挑戦は互いに独立です。挑戦によって部屋の情報が変化することはなく、部屋の情報を変更するのは種類 1 のイベントのみです。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 10^5
  • N + Q \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 0 \leq B_i \leq 10^9
  • 種類 1 のイベントにおいて、1 \leq i \leq N、0 \leq a \leq 10^9、0 \leq b \leq 10^9
  • 種類 2 のイベントにおいて、0 \leq s \leq 10^9
  • 種類 2 のイベントは 1 つ以上存在する
  • 入力はすべて整数である

入力

N Q
A_1 B_1
A_2 B_2
\vdots
A_N B_N
\mathrm{event}_1
\mathrm{event}_2
\vdots
\mathrm{event}_Q

1 行目には、部屋の個数 N とイベントの個数 Q がスペース区切りで与えられます。続く N 行のうち i 行目には、部屋 i のモンスターを倒すために必要な戦闘力 A_i と、倒したときに増加する戦闘力 B_i がスペース区切りで与えられます。続く Q 行では、イベントが次のいずれかの形式で与えられます。

  • 1 i a b
  • 2 s

出力

種類 2 のイベントごとに、高橋君が倒すことができるモンスターの数を、イベントが与えられた順に 1 行ずつ出力してください。

入力例 1

4 5
3 2
5 3
10 1
9 5
2 3
2 4
1 3 8 10
2 3
2 0

出力例 1

2
2
4
0

入力例 2

3 6
0 0
1 5
6 0
2 0
2 1
1 2 2 10
2 1
1 1 5 0
2 5

出力例 2

1
3
1
3

入力例 3

8 10
5 3
8 2
7 10
20 1
21 5
30 0
25 8
40 10
2 5
2 4
1 6 26 5
2 5
1 8 39 1
2 5
1 1 6 100
2 5
1 4 200 0
2 100

出力例 3

5
0
7
8
0
8

入力例 4

15 18
10 5
12 0
12 8
25 10
40 20
70 0
60 15
80 5
90 30
130 10
150 50
210 0
205 10
220 100
400 1
2 10
2 9
1 2 20 100
2 10
1 6 150 100
2 10
1 5 200 0
2 10
1 5 35 5
1 12 300 0
2 50
1 15 260 0
2 50
1 1 0 0
2 0
1 14 1000000000 0
2 1000000000
2 399

出力例 4

3
0
1
1
1
15
15
1
15
13

入力例 5

1 7
0 0
2 0
1 1 1000000000 1000000000
2 999999999
2 1000000000
1 1 0 1000000000
2 0
2 1

出力例 5

1
0
1
1
1

Score : 466 pts

Problem Statement

Takahashi challenges a dungeon. The dungeon has N rooms arranged in a row, numbered room 1, room 2, \ldots, room N in order from the entrance. Each room contains exactly one monster.

When Takahashi challenges the dungeon, he proceeds one room at a time starting from room 1, then room 2, room 3, \ldots, and must fight the monster in each room. He cannot skip any rooms. To defeat the monster in room i, his combat power before the battle must be at least A_i. Upon defeating a monster, his combat power increases by B_i. If he fails to defeat a monster, Takahashi ends his exploration there. The exploration also ends if he defeats all monsters.

Q events are given in order. There are two types of events:

  • 1 i a b: The information of the monster in room i is updated. From now on, the combat power required to defeat it becomes a, and the combat power gained upon defeating it becomes b.
  • 2 s: Takahashi challenges the dungeon starting from room 1 with an initial combat power of s. Based on the room information at that point, determine the number of monsters Takahashi can defeat.

Each challenge of type 2 is independent of the others. A challenge does not change the room information; only type 1 events modify room information.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 10^5
  • N + Q \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 0 \leq B_i \leq 10^9
  • In type 1 events, 1 \leq i \leq N, 0 \leq a \leq 10^9, 0 \leq b \leq 10^9
  • In type 2 events, 0 \leq s \leq 10^9
  • There is at least one type 2 event
  • All input values are integers

Input

N Q
A_1 B_1
A_2 B_2
\vdots
A_N B_N
\mathrm{event}_1
\mathrm{event}_2
\vdots
\mathrm{event}_Q

The first line contains the number of rooms N and the number of events Q, separated by a space. The following N lines each contain, for the i-th line, the combat power A_i required to defeat the monster in room i and the combat power increase B_i upon defeating it, separated by a space. The following Q lines each describe an event in one of the following formats:

  • 1 i a b
  • 2 s

Output

For each type 2 event, output the number of monsters Takahashi can defeat, one per line, in the order the events are given.

Sample Input 1

4 5
3 2
5 3
10 1
9 5
2 3
2 4
1 3 8 10
2 3
2 0

Sample Output 1

2
2
4
0

Sample Input 2

3 6
0 0
1 5
6 0
2 0
2 1
1 2 2 10
2 1
1 1 5 0
2 5

Sample Output 2

1
3
1
3

Sample Input 3

8 10
5 3
8 2
7 10
20 1
21 5
30 0
25 8
40 10
2 5
2 4
1 6 26 5
2 5
1 8 39 1
2 5
1 1 6 100
2 5
1 4 200 0
2 100

Sample Output 3

5
0
7
8
0
8

Sample Input 4

15 18
10 5
12 0
12 8
25 10
40 20
70 0
60 15
80 5
90 30
130 10
150 50
210 0
205 10
220 100
400 1
2 10
2 9
1 2 20 100
2 10
1 6 150 100
2 10
1 5 200 0
2 10
1 5 35 5
1 12 300 0
2 50
1 15 260 0
2 50
1 1 0 0
2 0
1 14 1000000000 0
2 1000000000
2 399

Sample Output 4

3
0
1
1
1
15
15
1
15
13

Sample Input 5

1 7
0 0
2 0
1 1 1000000000 1000000000
2 999999999
2 1000000000
1 1 0 1000000000
2 0
2 1

Sample Output 5

1
0
1
1
1