Description

We have a grid where the bottom-left corner is $(1,1)$. Let the cell in the $a$-th column from the left and the $b$-th row from the bottom be denoted as $(a,b)$.
Define direction $v$ as the direction obtained by rotating the east direction counterclockwise by $v \times 45^\circ$.

There are $n$ axis-aligned rectangles on the plane, each given by its bottom-left corner $(x_1,y_1)$ and top-right corner $(x_2,y_2)$.

We are given $m$ operations $(v,i,d)$, which mean: move the $i$-th rectangle in direction $v$ by $d$ units, and keep all intermediate rectangles generated during the movement (i.e., after each unit step, the new position is also recorded as a rectangle).

After all operations are performed, we need to answer $q$ queries $(x,y)$: output the number of rectangles that contain the point $(x,y)$.

Limitations

• $1 \le n \le 2.5 \times 10^5$
• $0 \le m \le 2.5 \times 10^5$
• $1 \le q \le 2.5 \times 10^5$
• $0 \le v \le 7$, $1 \le i \le n$
• $1 \le d \le 2.5 \times 10^5$
• All coordinates are guaranteed to always lie in the range $[1, 2.5 \times 10^5]$.
• Time limit: $8$ seconds, Memory limit: $1024$ MB.

Solution

First, apply a difference transformation to the problem, turning it into adding $1$ to line segments in $8$ directions and then querying the sum of preifx rectangles. Moreover, the $8$ cases can be reduced to $4$ basic types: $(+1,+0)$, $(+1,+1)$, $(+0,+1)$, and $(-1,+1)$.

For the first type, sweep over the invariant $y$-axis, use a Fenwick Tree (BIT) to support range add and range sum queries on the $x$-axis. For each step, add $1$ to the interval $[x, x+d)$ and then query the sum over $[1, x]$.

For the second type, note that the difference $x - y$ remains invariant during the move. Transform the coordinates $(x, y)$ into $(y, x - y)$ and $(x, y - x)$, then sweep twice similarly to the first type to cover all cases.

For the remaining two types, transform the coordinates into $(y, x)$ and $(y, -x)$ respectively, so that they correspond to the previous cases. The time complexity is $O(\log n)$ per operation.

Implementation advice: wrap the sweep line process and handle axis-aligned and diagonal movements in separate functions, otherwise the code may become overly complex. Also note that after coordinate transformation, the coordinate range may extend to $[-5 \times 10^5, 5 \times 10^5]$, so an offset should be added to avoid negative indices.