Квадрати#76

Квадрати (Editorial)

Поле величезне (m \le 10^9), тому перебирати всі квадрати неможливо. Але чорних клітинок лише n \le 10^5, а k \le 4 — і саме це рятує.

Ключове спостереження: чорна клітинка потрапляє лише в ті квадрати, чий лівий верхній кут задовольняє

\max(1,\, x-k+1) \le i \le \min(x,\, m-k+1), \qquad \max(1,\, y-k+1) \le j \le \min(y,\, m-k+1).

Таких кутів щонайбільше k^2 \le 16.

Отже, переберемо всі чорні клітинки і для кожної — усі її \le k^2 можливих квадратів, збільшуючи лічильник у хеш-таблиці, ключем якої є координати кута. Загалом у таблиці буде не більше n k^2 \le 1.6 \cdot 10^6 записів.

Після цього таблиця містить рівно ті квадрати, у яких є хоча б одна чорна клітинка, разом із точною кількістю чорних. Будуємо гістограму: для кожного значення лічильника t \ge 1 рахуємо, скільки квадратів його мають.

Залишається t = 0. Усього квадратів k \times k на полі рівно (m - k + 1)^2, тому

\mathrm{ans}[0] = (m-k+1)^2 - (\text{кількість різних ключів у таблиці}).

Не забудьте окремий випадок m < k: тоді жодного квадрата не існує і всі відповіді нульові.

Складність — \mathcal{O}(n k^2) у середньому. Величина (m-k+1)^2 сягає 10^{18}, тому обов'язково 64-бітний тип; ключ хеш-таблиці теж зручно пакувати у 64-бітне число як i \cdot (m+1) + j.