Будемо динамічно додавати точки та оновлювати відповіді. Спочатку відповіді на всі $$$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))$$$.