Rys. 1 Przykładowy kwadrat rozmiaru z czterema polami zabronionymi (zaznaczone krzyżykami). Największy pusty prostokąt ma rozmiar Poniższa tabelka przedstawia liczności pustych prostokątów dla wszystkich rozmiarów :

To zadanie nie powinno być nowością ani dla miłośników zadań olimpijskich (pojawiło się m.in. na IX Olimpiadzie Informatycznej jako zadanie pt. Działka), ani dla stałych czytelników Delty (omawialiśmy jego rozwiązanie w artykule Prostokąt arytmetyczny w numerze 3/2012). Co więcej, różne modyfikacje tego zadania pojawiały się też (i nadal pojawiają) na innych konkursach. Przykładowe modyfikacje mogą polegać na tym, że jesteśmy proszeni o znalezienie pustego prostokąta o największym obwodzie, liczby pustych prostokątów czy też sumarycznego pola powierzchni wszystkich pustych prostokątów. I choć główna idea rozwiązania wszystkich tych wersji zadania jest taka sama, to różnią się one w szczegółach, które każdorazowo trzeba dopracować. Tutaj przedstawimy dość ogólną metodę, która pozwoli nam bardzo łatwo rozwiązywać podobne zadania. A mianowicie pokażemy, jak wyznaczyć w sumarycznym czasie liczbę pustych prostokątów rozmiaru dla wszystkich wartości

Pole leżące na przecięciu -tego wiersza i -tej kolumny kwadratu będzie miało współrzędne Przede wszystkim dla każdego pola będziemy chcieli znać liczbę niezabronionych pól leżących powyżej niego (włącznie z tym polem); oznaczymy tę wartość przez Całą tablicę łatwo obliczyć w czasie gdyż jeśli pole jest zabronione oraz w przeciwnym przypadku. Dla uproszczenia zakładamy również, że wszystkie pola poza kwadratem są zabronione i

Rys. 2 Zacieniono trzy prostokąty, które reprezentują obszar dla pola Poniższa tabelka przedstawia zawartość stosu dla pól gdy

Rozwiązanie podzielimy na faz; w -tej fazie będziemy rozpatrywać prostokąty, których dolny bok zawiera pola z -tego wiersza. Ustalmy pewne pole i rozważmy wszystkie puste prostokąty, których prawy dolny róg znajduje się na tym polu. Zbiór wszystkich pól, w których może znajdować się lewy górny róg takiego pustego prostokąta, jest obszarem, którego górny obrys składa się z odcinków idących w prawo i do góry. Taki obszar będziemy reprezentowali jako sumę minimalnej liczby rozłącznych prostokątów o coraz większych wysokościach, których dolne boki dotykają -tego wiersza (Rys. 2). Rozmiary kolejnych prostokątów będziemy trzymać na stosie, co umożliwi nam łatwe uaktualnianie tej reprezentacji, jeśli będziemy przeglądać kolumny od lewej do prawej.

Stos będziemy trzymać w tablicy (wysokości i szerokości -tego prostokąta na stosie to odpowiednio oraz ), a liczbę jego elementów w zmiennej Poniższy pseudokod pokazuje, jak uaktualnić zawartość stosu dla pola aby odpowiadała ona polu Dopóki wysokość najwyższego prostokąta na stosie jest co najmniej tak duża jak to usuwamy go ze stosu. Następnie wrzucamy na stos prostokąt rozmiaru gdzie jest sumaryczną długością wszystkich usuniętych prostokątów plus 1.

Zauważmy, że każdy prostokąt usuwany ze stosu jest kandydatem na największy pusty prostokąt. Co więcej, wystarczy, że rozpatrzymy tylko tych kandydatów. Ponieważ dla ustalonego liczba operacji wykonanych na stosie jest gdyż wrzucamy na niego elementów, zatem cały algorytm działa w czasie

Aby wyznaczyć liczbę pustych prostokątów wszystkich rozmiarów, postąpimy nieco sprytniej. Zachowamy następujący niezmiennik: jeśli znajdujemy się na polu to znaczy, że policzyliśmy już te puste prostokąty, których prawy dolny róg jest na polu dla i jednocześnie nie są one zawarte w obszarze dla pola

Rys. 3 Rozważając pole usuwamy element ze stosu. Musimy wtedy policzyć prostokątów mających prawy dolny róg na polu a lewy górny w ciemno zacienionym obszarze. Jest tam prostokątów rozmiaru dla i
Następnie usuwamy element ze stosu, co powoduje zliczenie 15 prostokątów z jasno zacienionego obszaru ( prostokątów rozmiaru dla ).

Zatem zwiększanie obszaru (poprzez wrzucanie nowych elementów na stos) nigdy nie będzie zmieniać liczności rozważonych pustych prostokątów, natomiast usuwanie elementów ze stosu może powodować konieczność aktualizacji. Wszystkie pola usuniętego prostokąta które znajdują się w odległości co najmniej od wiersza na pewno zostaną usunięte z obszaru (zakładamy przy tym, że ). Musimy zatem policzyć puste prostokąty zawarte w prostokącie które przestaną być w tym obszarze zawarte, czyli ich lewy górny róg jest jednym z pól, które zostaną usunięte z obszaru. Te prostokąty mają wysokości od do oraz szerokości od 1 do przy czym prostokątów o rozmiarze jest (Rys. 3).

Należy też uważnie rozważyć przypadek, gdy dla danego pola usuwamy więcej niż jeden element ze stosu. Wtedy szerokość aktualnie usuwanego elementu należy zwiększyć o szerokości usuniętych poprzednio (wygodnie jest tu korzystać z wprowadzonej już zmiennej ).

Jeśli zatem liczności pustych prostokątów będziemy zapisywać w tablicy (gdzie oznacza liczbę pustych prostokątów rozmiaru ), to mamy do rozwiązania następujący problem: dla danych liczb i chcemy szybko wykonywać operację zwiększania komórek o wartość dla oraz Nie możemy, oczywiście, pozwolić sobie na zrobienie tego zupełnie naiwnie. Zakładając, że początkowo w tablicy są same zera, zastosujemy następujący trik: do komórki wpiszemy 1, a do komórki wpiszemy Następnie niezależnie w każdej kolumnie tablicy obliczymy sumy prefiksowe. To spowoduje, że jedynki znajdą się w komórkach dla (a zniknie). Następnie w każdym wierszu obliczymy "trochę lepsze" sumy sufiksowe, które każdą jedynkę w komórce zamienią na ciąg liczb w komórkach Po takich manipulacjach tablica ma wartości zgodne z pojedynczą operacją zwiększania.

Nietrudno się przekonać, że jeśli chcemy wykonać więcej niż jedną operację zwiększania, to możemy najpierw zwiększyć wszystkie komórki o jeden i zmniejszyć odpowiadające im komórki o jeden, a dopiero na sam koniec jeden raz obliczyć powyższe sumy. Łącznie zajmie to czas a pseudokod algorytmu może wyglądać następująco:

Jako ćwiczenie dla Czytelnika proponujemy modyfikację tego algorytmu, aby dla każdego rozmiaru wyznaczał liczbę maksymalnych pustych prostokątów, czyli takich, które nie są zawarte w żadnym większym pustym prostokącie.