Автор задачі: | Фейса Богдан |
Задачу підготував: | Фейса Богдан |
Розбір написав: | Фейса Богдан |
Спочатку зведемо задачу до пошуку найбільшої підматриці лише з одиничок. Для цього ми перетворимо кожне число в матриці за принципом:
a_{i,j}=\begin{cases}0 \text{ якщо число не належить проміжку }[l,r]\\1\text{ якщо число належить проміжку }[l,r]\end{cases}
Зафіксуємо ліву межу підматриці, яку ми вибиратимемо в позиції (тобто для кожного рядка будемо дивитись лише на числа після позиції ). Для кожного рядка знайдемо кількість наступних нулів у цьому рядку.
Тепер ми знаємо для кожного рядка, яку праву межу ми можемо вибрати для нього. Запишемо допоміжний масив , в якому ми будемо зберігати відстань між лівою і можливою правою границею для рядка в елементі b_i.
Тепер, для фіксованої лівої границі ми будемо перебирати праву границю наступним чином:
Виберемо "опорний" рядок . Іншими словами, скажемо, що відстань між лівою та правою границями буде рівна b_x. Тоді верхньою та нижньою границями будуть рядки (l<x<r), в яких b_l<b_x та b_r<x при, тому що на відрізку b_{l+1}...b_{r-1} всі елементи є не меншими за b_x. Для кожного ми можемо знайти такі сумарно за лінійний час, використовуючи стеки. При фіксованій лівій границі та рядку , ми можемо порахувати площу оптимальної підматриці як b_x\cdot (r_x-l_x-1) (ми віднімаємо одиницю через те, що на проміжку [l+1,r-1] є рівно r-l-1 цілих чисел).
Повертаючись до нашої задачі, ми повинні рухати ліву границю підматриці й для кожної можливої границі обраховувати за лінійний час підматрицю найбільшої площі з фіксованою лівою границею. Тому сумарний час роботи нашої програми становитиме .