Мозаїчна арка#13114

Мозаїчна арка (Розбір)

Перефарбування. Нехай x_{i,j} — це колір клітинки , якщо i + j парне, і протилежний колір інакше. У двох сусідніх за стороною клітинок парність i + j різна, тому їхні кольори різні тоді й лише тоді, коли їхні значення рівні. Сусідні клітинки -фігури є сусідніми за стороною, отже, -фігура гарна тоді й лише тоді, коли всі її клітинки мають однакове .

Нехай d_{i,j} — кількість клітинок у найдовшому вертикальному відрізку з однаковим , що починається в і йде вниз (обчислюємо від нижнього рядка вгору). Зафіксуємо r, c_1, c_2. Клітинки (r, c_1), \ldots, (r, c_2) мають лежати всередині однієї серії рядка — максимального відрізка з однаковим ; тоді -фігура з цими r, c_1, c_2 і заданим гарна тоді й лише тоді, коли k \le d_{r,c_1} і k \le d_{r,c_2}. Усі a_{i,j} додатні, тож для фіксованих r, c_1, c_2 найкраще взяти k = \min(d_{r,c_1}, d_{r,c_2}), якщо воно не менше за .

Групування пар за . У широкій таблиці пар (c_1, c_2) забагато, тому згрупуємо їх за . Нехай P_j = a_{r,1} + \ldots + a_{r,j} і L_k(c) = a_{r+1,c} + \ldots + a_{r+k-1,c} (друге обчислюється за через префіксні суми по стовпцях). -фігура (r, c_1, c_2, k) має вагу

\bigl(L_k(c_1) - P_{c_1-1}\bigr) + \bigl(P_{c_2} + L_k(c_2)\bigr).

Зафіксуємо серію і переберемо різні значення k \ge 2 серед d_{r,c} у цій серії. Для кожного назвемо активними стовпці серії з d_{r,c} \ge k і пройдемо їх зліва направо: для активного c_2 додаємо його праву дужку до максимуму лівої дужки за активними c_1 \le c_2 - 2 — це префіксний максимум, який підтримуємо другим вказівником. Кожне отримане значення є вагою гарної -фігури (бо k \le \min(d_{r,c_1}, d_{r,c_2})), а кожна пара стовпців отримує своє найкраще значення в проході з k = \min(d_{r,c_1}, d_{r,c_2}). Отже, відповідь — максимум за всіма проходами, або , якщо жоден прохід не знайшов пари.

Складність. Серія ширини має не більше \min(w, n) різних значень , а кожен прохід займає часу (якщо тримати активні стовпці у зв'язному списку й після проходу видаляти ті, де d_{r,c} = k, він стає ще швидшим). Сумарна ширина серій рядка не перевищує , тож рядок коштує O(m \cdot \min(n, m)), а складність — O(nm \cdot \min(n, m)) \subseteq O((nm)^{3/2}) на тестовий випадок, плюс сортування значень у кожній серії. Відповідь може перевищувати 10^{14}, тому потрібні 64-бітні цілі числа.