2021 Azerbaijan, Republic Informatics Olympiad, Semifinal, March 8
A linear network of n computers was installed in the big data center. All computers are numbered with integers sequentially from 1 to n. There is a direct communication between computers with neighbouring numbers. It is clear that in such a network it is possible to directly or indirectly exchange data between any two computers. However, due to the intensity of the operations, some computers sometimes fail. In such cases, the communication between some computers is interrupted and data transfer becomes impossible.
You are asked to find out the number of groups in the network at the moment. A group is the maximum number of active computers where any two computers from the same group have communication with each other. Also, a group can consist of only one computer.
You need to answer q queries. In each of the queries, either the number of the computer that has just failed is given, or it is necessary to count the number of groups.
For a better understanding of the problem, below is an explanation for the example.
The first line contains two integers n and q. The following q lines contain queries.
Each query starts with a number T indicating the type of request. T = 1 is always followed by the number L of the failed computer.
For each query of the 2-nd type, it is necessary to print the number of groups in the network at the current moment in a separate line.
- 1 ≤ n ≤
- 1 ≤ q ≤
- T = 1, 2
- 1 ≤ L ≤ n
This problem consists of 3 subtasks:
|1||n ≤ ||14 points|
|2||n ≤ ||37 points|
|3||No additional restrictions||49 points|
1 2 3 4 -- Initial state of the network. The number of groups is 1.
1 x 3 4 -- The state of the network after the failure of the computer number 2. Number of groups - 2.
1 x 3 x -- The state of the network after the failure of the computer number 4. Number of groups - 2.
1 x 3 x -- The state of the network after the failure of the computer number 2. Number of groups - 2.
Note: the requests for computer failure may be repeated.
4 6 1 2 2 1 4 2 1 2 2
2 2 2