PROBLEM LINK:
Author: Ildar Gainullin
Tester: Oleksandr Kulkov
Editorialist: Oleksandr Kulkov
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Segment tree or sqrt-decomposition, DSU
PROBLEM:
Given a set of diamonds with radius r on the plane. You are to proccess connectivity queries between those diamonds.
QUICK EXPLANATION:
Compute the transform \begin{cases}x'=x+y,\\y'=x-y.\end{cases} to solve problem with squares instead of diamonds. Find any square center in each of squares \begin{cases}[x-2r,x] \times [y-2r,y],\\ [x-2r,x] \times [y, y+2r],\\ [x, x+2r] \times[y-2r,y],\\ [x,x+2r]\times[y,y+2r]. \end{cases} and connect them in DSU with the new square.
EXPLANATION:
The set \left\{(a, b): |a-x|+|b-x| \leq r\right\} forms a diamond with center in (x,y). By rotating it on 45^\circ we can turn it into square. Transform \begin{cases}x'=x+y,\\ y'=x-y.\end{cases} makes such rotation with additional stretching. Considering that |x-a|+|y-b|=\max\left(\begin{matrix}x-a+y-b,\\ a-x+y-b, \\ x-a + b - y, \\ a - x + b - y.\end{matrix}\right)=\max\left(\begin{matrix}|(x+y)-(a+b)|,\\ |(x-y)-(a-b)|.\end{matrix}\right)=\max(|x'-a'|, |y'-b'|) we can see that the diamond will be transformed into square \left\{(a',b'):\max(|a'-x'|,|b'-x'|)\leq r\right\}.
Note that squares with centers (x_1, y_1) and (x_2, y_2) will overlap iff \max(|x_1-x_2|,|y_1-y_2|) \leq 2r. Given that and using disjoint set union we can find for new square every old one which is directly connected to it and add corresponding edge into DSU. This will solve problem in O(n^2).
Instead of this we can make the following observation: consider DSU to be built correctly for already added squares. Now we want to add square with center in (x,y). We want it to be in the same connected component with all the squares having center in [x-2r,x+2r]\times[y-2r,y+2r]. Consider (a,b) \in [x-2r,x]\times[y-2r,y] to be some already added center of square. By correctness assumption it is in the same connected component with all square centers from [a-2r,a+2r]\times[b-2r,b+2r] \supset [x-2r,x]\times[y-2r,y]. Thus connecting (x,y) with arbitrary (a,b)\in[x-2r,y-2r] will make it to be in the same connected component with every square centered in [x-2r,y-2r]. So it will be enough for us to find some members of all quarters of [x-2r,x+2r]\times[y-2r,y+2r] and connect them with (x,y) in DSU to make DSU correct.
The only question left is how to find any representative of [x_1, x_2]\times[y_1, y_2] square. This can be simply done by using segment tree having in each vertex v corresponding to the segment [l,r] the set of vertices with x \in [l, r]. Then we can split [x_1,x_2] segment in O(\log n) vertices of segment tree and in each vertex to find the lower bound of y_1 in O(\log n) and check it to be not greater than y_2. Using this approach we can get the overall complexity of O(n \log^2 n).
ALTERNATIVE SOLUTION:
There is more complicated O(n \sqrt n) approach which can be found in author’s solution.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.