National Olympiad in Informatics, China, 2008
There is a beautiful fairy tale: Once upon a time in a far away land by the edge of the world, there existed a "Candy Kingdom". This nation is filled with skyscrapers; meanwhile, the little trails, flowers, and grass are all made out of candy. What's more magical is that the sky is filled with rainbow colored candy clouds floating about. Very often, heavy candy rain will pour onto the ground. The red colors are strawberry candy, the yellow colors are lemon, the green colors are mint, the black colors are chocolate, and so on. The children of Candy Kingdom will frequently hold open pouches of all sizes to catch the candy pieces that fall from the sky, bringing them home for their friends to enjoy.
Having a very big sweet tooth, little Z longs to be able to visit this fairy tale kingdom. As the old saying goes, what you think about in the day, you will dream about during the night. So one night, little Z dreamed that he has arrived in Candy Kingdom. He discovered that at any given moment, all of the clouds in the sky will have different colors. These different colored clouds continuously drop candies of corresponding colors. What's even more interesting is that all of the clouds are in constant back and forth motion. There's no harm in imagining that there are borders to the sky, which is why the clouds just happen to be moving back and forth between the two borders of the sky. During each unit of time, a cloud moves one unit of distance either to the left or to the right. When a cloud hits the left border of the sky, it will change its direction and start moving to the right; when a cloud completely moves past the right border of the sky, it will change its direction and start moving to the left.
We may as well think of the sky as a Cartesian coordinate plane, where clouds are represented by line segments (which may degenerate to points):
In the figure above, we set the left border of the sky to be and the right border to be . The figure contains a total of clouds. The cloud labeled is just changing its direction to move rightwards. The cloud labeled is just changing its direction to move leftwards. The vertical coordinates of the clouds may be ignored, for the clouds will never affect each other during their movement process.
Little Z noticed that new clouds will continuously form in the sky (during some time, at some starting position, moving in some direction), and some clouds after moving for a certain time will disappear from the sky. While clouds are in motion, candy will continuously fall from them. Little Z decided to bring many bags to catch the falling candy. Bags have unlimited capacities, but the size of their openings are limited. For example at time , little Z carries a bag which has an opening spanning the horizontal range . If contains a position where candy falls, then the bag will be able to catch the candy. In extreme cases, the range of the bag's opening can be a point such as or , but the bag will still be able to catch candy at the corresponding positions. It is generally known that the amount of candy one can catch is rather larger, so little Z would like to know for each time (the moment he pulls out a bag) how many different colors of candy can his bag catch? The falling times of the candy are negligible.
Input Specification
The first line contains two positive integers and , representing the total number of events and the sky's "boundary", respectively.
For the following lines, each line describes one event. All events
happen in the input order. The first number of each line (,
, or ) specifies the type of event that happens. There are three types
of events: Insert
, Query
, and Delete
. Their formats are as
follows:
Event Type | Input Format | Explanation |
---|---|---|
Insert (A new cloud appears in the sky) |
1 T_i C_i L_i R_i D_i |
At time , a new cloud of color spanning the range will appear in the sky. The initial direction of the cloud may be leftwards or rightwards . These parameters will satisfy , and . The data guarantees that at any given moment, the sky will not contain two clouds that are the same color. |
Query (Determine how many different colors of candy a bag can catch) |
2 T_i L_i R_i |
At time , little Z uses a bag with an opening that spans the range to catch candy. He would like to know how many different colors of them he can catch. The parameters will satisfy . |
Delete (A cloud disappears from the sky) |
3 T_i C_i |
At time , the cloud colored will disappear from the sky. The data guarantees that the sky contains a cloud with color at that time. |
Output Specification
For each Query
event, output one line containing one integer — the
number of different colors of candy that can be caught by the
corresponding bag.
Sample Input
10 10
1 0 10 1 3 -1
2 1 0 0
2 11 0 10
2 11 0 9
1 11 13 4 7 1
2 13 9 9
2 13 10 10
3 100 13
3 1999999999 10
1 2000000000 10 0 1 1
Sample Output
1
1
0
2
1
Explanation
There are total events, including Insert
events, Query
events, and Delete
events.
At time , a cloud of color appears in the sky, initially spanning
the range and moving left.
At time , a bag with the range can catch candy of color (with
the cloud at ).
At time , a bag with the range can catch candy of color
(with the cloud at ).
At time , a bag with the range cannot catch any candy of color
(with the cloud at ).
At time , a cloud of color appears in the sky, initially spanning
the range and moving right.
At time , a bag with the range can catch candy of color
(with the cloud at ) and candy of color (with the cloud at ) for different colors.
At time , a bag with the range can only catch candy of color
(with the cloud at ), but cannot catch any candy of color
(with the cloud at ).
At time , the cloud of color disappears from the sky.
At time , the cloud of color disappears from the sky.
At time , another cloud of color appears in the sky,
initially spanning the range and moving right.
Constraints
All of the data will satisfy and .
The data guarantees that forms a non-decreasing sequence
. For all of the Insert
events, let represent the length of each cloud.
Test Case | |||
---|---|---|---|
Problem translated to English by .
Comments