Квадрати

Будемо динамічно додавати точки та оновлювати відповіді. Спочатку відповіді на всі $$$t$$$ рівні нулю, крім $$$t=0$$$ (бо точок немає). Для $$$t=0$$$ відповідь $$$(n-k+1)^2$$$.

Будемо також зберігати кількість чорних точок у кожному квадраті.

Коли ми додаємо певну точку, нам потрібно знайти всі квадрати $$$k \times k$$$, у яких знаходиться ця точка. Таких квадратів буде не більше $$$k^2$$$. Нехай кількість чорних точок для певного квадрата буде $$$d$$$. Тоді відповідь для $$$t=d$$$ зменшиться на $$$1$$$, а для $$$t=d+1$$$ збільшиться на один.

Сумарна асимптотика: $$$O(n k^2 \log (n k^2))$$$.