New Year's '16 P8 - S-NO-wall

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type

What's more fun than building snowmen? Building snow walls! A snow wall is a simple yet elegant structure, constructed with the most refreshing element of pure white blocks of snow. Snow walls are not too difficult to make, and are extremely rewarding as the length of the wall grows!

On this fine day, there are many people working on «The Great Snow Wall», a gigantic snow wall that will be made of N blocks of snow all in a line on FatalEagle's lawn. Sometimes throughout the day, FatalEagle hears the indefatigable project overseer cheesecake shouting outside. Each time cheesecake is shouting, he is either ordering for all the blocks between position l and position r (inclusive) to be constructed, or deconstructed because it's not up to quality. The height of the wall will always be at most one, so workers only need to construct blocks that are not already up. Each time cheesecake calls for a part of the wall to be constructed/deconstructed, his trusty workers finish the work instantaneously.

FatalEagle would like to ensure that «The Great Snow Wall» never gets completed, so he wants to know how many blocks of snow are in the longest completed section of the wall whenever cheesecake yells. Sometimes, this number is too disconcerting, in which case FatalEagle will call his wall dismantling drone to destroy the longest completed section of the wall (he may do this multiple times in succession). If there is a tie, the drone will only destroy the section closest to the left. Can you help FatalEagle to keep track of the giant wall on his lawn?

Constraints

Subtask 1 [20%]

1 \le N, Q \le 20\,000

Subtask 2 [80%]

1 \le N, Q \le 100\,000

Input Specification

The first line of input will contain two integers, N and Q.

The next Q lines will each contain the following:

The first integer of each line will be T.

  • If T = 0, a deconstruction has been made. The next two integers will be l and r (1 \le l \le r \le N), the range which has been deconstructed.
  • If T = 1, a construction has been made. The next two integers will be l and r (1 \le l \le r \le N), the range which has been constructed.
  • If T = 2, FatalEagle puts his dismantling drone to action.

Output Specification

After each construction/deconstruction, output one integer, the span of the maximum contiguous completed section of the wall.

Sample Input

10 5
1 1 10
0 4 6
0 4 7
2
1 4 10

Sample Output

10
4
3
7

Explanation for Sample Output

Let's outline what happened (0 will represent unbuilt blocks, 1 will represent built):

1111111111 In the first update, the entire wall is built.

1110001111 In the second update, cheesecake feels the wall is … off, so he orders blocks 4 to 6 to be destroyed.

1110000111 In the third update, blocks 4 to 7 are ordered to be destroyed, but 4 to 6 are already missing, so just block 7 gets taken down.

0000000111 A drone dismantling is then in place. Since there is a tie, the drone takes down the first three blocks.

0001111111 Finally, cheesecake orders every block from 4 to 10 to be put up.


Comments