Editorial for Bubble Cup V8 I Robots protection

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

To solve this problem, we should first take a look at one easier problem. Consider having the same problem statement, but with rectangles instead of triangles. The solution to this problem is pretty straightforward. We will store a matrix representing points in our coordinate system. For each type 1 query, given the rectangle $((x_{ul}, y_{ul}), (x_{ur}, y_{ur}), (x_{ll}, y_{ll}), (x_{lr}, y_{lr}))$ $((x_{u l}, y_{u l}), (x_{u r}, y_{u r}), (x_{l l}, y_{l l}), (x_{l r}, y_{l r}))$ , we would add $-1$ $- 1$ to the points $(x_{ul}, y_{ul}+1)$ $(x_{u l}, y_{u l} + 1)$ and $(x_{lr}+1, y_{lr})$ $(x_{l r} + 1, y_{l r})$ , and $1$ $1$ to the points $(x_{ll}, y_{ll})$ $(x_{l l}, y_{l l})$ and $(x_{ur}+1, y_{ur}+1)$ $(x_{u r} + 1, y_{u r} + 1)$ . Notice that we expanded the given rectangle when adding $+1$ $+ 1$ s and $-1$ $- 1$ s, this is because the point is considered in the rectangle even when it is on the border! This way, when a type 2 query is received, to find the answer we simply sum every value in the rectangle $(0, 0)$ $(0, 0)$ to $(x, y)$ $(x, y)$ . Since simply summing the points in rectangles is $\mathcal O(n^2)$ $O (n^{2})$ , we should use binary indexed tree for this, hence getting the sufficient time complexity $\mathcal O(\log^2 n)$ $O (\log^{2} n)$ per query.

We will use this approach with some modification to solve the original problem. For handling the triangles we need to introduce new coordinate systems. Depending on the type of triangle (types 1 and 4 are analogous, so are types 2 and 3) we will make two new coordinate systems, where the corresponding hypotenuses are parallel to one axis. For types 2 and 3, point $(x, y)$ $(x, y)$ in the original coordinate system would map to $(x+y, y)$ $(x + y, y)$ , and for types 1 and 4, point $(x, y)$ $(x, y)$ would map to $(x+n-y-1, y)$ $(x + n - y - 1, y)$ , where $n$ $n$ is the size of the coordinate plane given in the input.

The problem is now somewhat abstracted to the simple rectangle problem. This time we will need three matrices, one representing the original coordinate system and two representing the introduced coordinate systems. For each triangle we need to border it with $+1$ $+ 1$ s and $-1$ $- 1$ s, similarly as in the rectangle case, only using 2 matrices for each triangle. When adding border for the cathetus we use the original coordinate system and for the hypotenuse we need one of the two introduced coordinate systems, depending on the type of the triangle. Remember, the point belongs to the triangle even when it is on one of catheti or hypotenuse, so be careful.

For calculating the answer for type 2 query, we need to sum the values in the rectangle from $(0, 0)$ $(0, 0)$ to $(x, y)$ $(x, y)$ in all three matrices (of course, $(x, y)$ $(x, y)$ needs to be mapped accordingly to the coordinate system each matrix represent). Again, to not exceed time limit we need to use binary indexed trees.

Since we are using binary indexed tree, the time complexity of this solution is $\mathcal O(Q \log^2 N)$ $O (Q \log^{2} N)$ .

Comments

There are no comments at the moment.