Разбор задачи "D. Рыцари".
Обозначим количество заборов окружающих опорную точку номер i через cnti. Также обозначим через cntij - количество заборов окружающих и точку i, и точку j. Тогда ответ для запроса (i, j) равен cnti + cntj - cntij. Понятно, что мы можем вычислить все значения cnti за время O(n * m). Проблема в быстром вычислении величины cntij. И тут предполагалось два решения: простое и не очень. Простое заключается в следующем: заведём для каждой точки i битсет, j-й бит которого равен 1 если j-й забор окружает точку номер i. Тогда очевидно cntij = count(zi & zj), где count(a) - количество единичек в битсете a. Теперь другое решение. Добавим ещё один забор с центром в (0, 0) и бесконечного радиуса. Построим граф вершинами которого являются заборы следующим образом: проведём дугу из i в j, если i-й забор это забор минимального радиуса окружающий забор номер j. Очевидно мы получим ориентированное дерево с корнем в заборе бесконечного радиуса. Также для каждой опорной точки найдём idxi - номер забора минимального радиуса окружающего i-ю опорную точку. Тогда cntij = distij + distji, где distij - расстояние от вершины i до наименьшего общего предка вершин i и j. С реализацией проблем не должно было возникнуть, т.к. в первом решении можно было либо самому написать битсет, либо воспользоваться стандартным битсетом (для тех кто пишет на С++), а во втором можно было предподсчитать все lca за O(n2).
pre-process the relation between central points and circles(inside/outside a circle) O(N2).
then answer the query in O(M), given 2 points, check which circles contain exactly 1 point outside the circle and 1 point inside the circle.
Total Complexity: O(N2 + QM) which is still ok for 2 sec
and total complexity O(NM+QM)
For each query (i, j), count the number of circles such that exactly one of control center i or control center j is inside the circle, and that's the answer.
https://codeforces.com/contest/33/submission/46096711
Why?
If both i and j are within a circle, there is no need to go over the fence. If they are both outside, there is no need. If exactly one of them is outside, they definitely need to go over that fence. O(MK)