8619: Counting Fish Again
内存限制：512 MB
时间限制：3 S
题面：传统
评测方式：Special Judge
上传者：
提交：0
通过：0
题目描述
Many years later, as he faced the Nowcoder Multi-University Training Contest, ACMer NIO was to remember that distant afternoon when his coach took him to count fish.
In a famous fish-counting problem in 2019, OIer NIO was asked to count the number of fish in 2D space. Unfortunately, the characteristics of fish were too complex, making counting them an almost impossible task. So let's look at this simplified fish-counting problem.
In this problem, NIO is given an infinite grid graph. And the god of fish will perform mmm operations on it. Assuming the coordinates of the bottom left corner of the grid graph are (0,0)(0,0)(0,0), there are two types of operations:
- 1 x1 y1 x2 y21\ x_1\ y_1\ x_2\ y_21 x1 y1 x2 y2 : Draw a segment between (x1,y1)(x_1,y_1)(x1,y1) and (x2,y2)(x_2,y_2)(x2,y2). It is guaranteed that x1+y1=x2+y2x_1+y_1=x_2+y_2x1+y1=x2+y2, and the drawn segments do not overlap with the existing ones.
- 2 x1 y1 x2 y22\ x_1\ y_1\ x_2\ y_22 x1 y1 x2 y2 : Erase a segment between (x1,y1)(x_1,y_1)(x1,y1) and (x2,y2)(x_2,y_2)(x2,y2). Still, x1+y1=x2+y2x_1+y_1=x_2+y_2x1+y1=x2+y2, and the segment alrealy exists in the grid graph.
- It consists of a square and an equilateral right triangle, and the triangle's right-angle vertex coincides with one vertex of the square.
- The length of the right-angle side of the triangle is equal to the square's side length.
Note that the original segments of the grid graph can also be part of a fish.
输入格式
The first line contains a single integer mmm (1≤m≤1061 \leq m \leq 10^61≤m≤106), indicating the number of operations.
Each of the next mmm lines contains five integers op,x1,y1,x2,y2op,x_1,y_1,x_2,y_2op,x1,y1,x2,y2 (1≤op≤21 \leq op \leq 21≤op≤2, 0≤ x1, x2, y1, y2≤1060 \leq\ x_1,\ x_2,\ y_1,\ y_2 \leq 10^60≤ x1, x2, y1, y2≤106, x1≠x2x_1\not= x_2x1=x2, x1+y1=x2+y2x_1+y_1=x_2+y_2x1+y1=x2+y2), indicating the operation and the segment between (x1,y1)(x_1,y_1)(x1,y1) and (x2,y2)(x_2,y_2)(x2,y2).
Each of the next mmm lines contains five integers op,x1,y1,x2,y2op,x_1,y_1,x_2,y_2op,x1,y1,x2,y2 (1≤op≤21 \leq op \leq 21≤op≤2, 0≤ x1, x2, y1, y2≤1060 \leq\ x_1,\ x_2,\ y_1,\ y_2 \leq 10^60≤ x1, x2, y1, y2≤106, x1≠x2x_1\not= x_2x1=x2, x1+y1=x2+y2x_1+y_1=x_2+y_2x1+y1=x2+y2), indicating the operation and the segment between (x1,y1)(x_1,y_1)(x1,y1) and (x2,y2)(x_2,y_2)(x2,y2).
输出格式
For each query, output an integer in a single line indicating the number of fish in the graph.
输入样例 复制
3
1 0 4 2 2
1 2 2 4 0
2 1 3 4 0输出样例 复制
4
12
1数据范围与提示
Here is the explanation of the example.
First, the god of fish draws a segment between (0,4)(0,4)(0,4) and (2,2)(2,2)(2,2).
As highlighted in the picture, there are 444 fish in the graph.
Then, the god of fish draws a segment between (2,2)(2,2)(2,2) and (4,0)(4,0)(4,0).
As highlighted in the picture, there are 888 new fish in the graph, so there are 121212 fish in total.
Finally, the god of fish erases the segment between (1,3)(1,3)(1,3) and (4,0)(4,0)(4,0).
As highlighted in the picture, there is only 111 fish left in the graph.
First, the god of fish draws a segment between (0,4)(0,4)(0,4) and (2,2)(2,2)(2,2).
As highlighted in the picture, there are 444 fish in the graph.
Then, the god of fish draws a segment between (2,2)(2,2)(2,2) and (4,0)(4,0)(4,0).
As highlighted in the picture, there are 888 new fish in the graph, so there are 121212 fish in total.
Finally, the god of fish erases the segment between (1,3)(1,3)(1,3) and (4,0)(4,0)(4,0).
As highlighted in the picture, there is only 111 fish left in the graph.