Fajny płot

Podzadanie 4

Gdy wszystkie $h_i$ są równe, na wejściu jest tak naprawdę jeden długi prostokąt. Liczba podprostokątów w prostokącie o wysokości $H$ oraz szerokości $W$ wynosi $T_{H,W}=(\genfrac{}{}{0ex}{}{H+1}{2})\cdot (\genfrac{}{}{0ex}{}{W+1}{2})$, ponieważ niezależnie można wybrać przedział współrzędnych $X$ oraz $Y$, z których będzie się składał prostokąt. Można to obliczyć w czasie $O(1)$.

Podzadanie 5

W tym podzadaniu zachodzi $h_1\le h_2\le \cdots \le h_N$.

Niech $W_i=\sum _{j=i}^N{w}_i$. Odpowiedzią jest $\sum _{i=1}^N{T}_{h_i,W_i}-T_{h_{i-1},W_i}$, gdzie $h_0=0$. Wynika to z tego, że w $i$-tym kroku są wliczane prostokąty, których lewy górny róg ma współrzędną $Y$ z przedziału $(h_{i-1},h_i]$.

Podzadanie 6

Dla $N\le {10}^3$ można dla każdych $1\le i\le j\le N$ policzyć liczbę podprostokątów, których lewy brzeg znajduje się w $i$-tym prostokącie, a prawy w $j$-tym.

Dla $i\ne j$ liczba ta wynosi $T_{H,W}-T_{H,W-w_i}-T_{H,W-w_j}+T_{H,W-w_i-w_j}$, gdzie $H$ jest minimalną wysokością na przedziale $[i,j]$, a $W$ jest sumą szerokości na tym przedziale. Wynika to z prostego zastosowania zasady włączeń i wyłączeń po tym, gdzie znajdują się brzegi podprostokąta.

Daje to rozwiązanie w złożoności $O(N^2)$.

Podzadanie 7 -- rozwiązanie od góry do dołu (find-union)

Będziemy zamiatać prostokąty od góry do dołu, czyli w kolejności nierosnących $h_i$. W momencie, gdy dany prostokąt zostanie już rozpatrzony, to za pomocą struktury dla zbiorów rozłącznych (find-union) zostanie on złączony z sąsiednimi prostokątami, które zostały już zamiecione (można to interpretować jako obniżanie zamiecionych prostokątów do poziomu miotły i rozpatrywanie ich razem). Przy czym poza informacją o złączonych prostokątach trzeba utrzymywać ich sumę długości.

W momencie, gdy prostokąt staje się zamieciony, za pomocą utrzymanych struktur danych można policzyć liczbę prostokątów dotykających tego prostokąta i być może tylko inne, już zamiecione prostokąty. Daje to niezmiennik, że po zamieceniu prostokąta, policzony wynik to liczba podprostokątów wśród zamiecionych prostokątów.

Daje to rozwiązanie w złożoności $O(n\log n)$ przez posortowanie liczb $h_i$ (czynnik algorytmu Find-Union nie został wliczony do złożoności, ponieważ jest mniejszy).

Podzadanie 7 -- rozwiązanie od lewej do prawej (stos)

Gdy rozpatrujemy jakiś prawy dolny róg podprostokąta, zbiór wszystkich możliwych poprawnych lewych górnych rogów jest sumą pewnych rozłącznych, stykających się prostokątów o rosnących wysokościach. Podsuwa to pomysł, aby utrzymywać stos takich prostokątów po rozpatrzeniu prostokątów z wejścia od $1$ do $i$.

Żeby pomysł zadziałał, należy wynik dla $i$ zdefiniować jako liczbę podprostokątów przechodzących wśród prostokątów $1,2,\dots ,i$, ale nie przechodzących przez prostokąty znajdujące się na stosie.

Aby na końcu otrzymać wynik dla całego zadania, wystarczy zasymulować jeszcze dodawanie prostokąta o rozmiarach $(0,0)$, aby pozbyć się prostokątów na stosie.

W momencie, gdy mamy stos dla $i-1$ i rozpatrujemy dodawanie $i$-tego prostokąta z wejścia, będziemy potencjalnie ze stosu zdejmować prostokąty i dodawać odpowiednią liczbę do wyniku. Niech $H\times W$ będzie rozmiarem prostokąta na wierzchu stosu.

• Jeżeli $h_i=H$, to wystarczy przedłużyć szerokość prostokąta na wierzchu stosu o $w_i$.
• Jeżeli $h_i>H$, to wystarczy wrzucić prostokąt $h_i\times w_i$ na wierzch stosu.
• Jeżeli $h_i<H$, to trzeba zrzucić pewną ilość prostokątów z wierzchu stosu aż do momentu, gdy $h_i$ będzie większe równe wysokości prostokąta na wierzchu stosu. Przy każdym zrzucaniu akumulujmy długości zrzuconych prostokątów i rozwiązaniem analogicznym do \textit{podzadania 5} zliczamy wkład do wyniku nowych prostokątów nie znajdujących się już na stosie.

Daje to rozwiązanie w zamortyzowanej złożoności $O(N)$, ponieważ zostanie wykonanych co najwyżej $N+1$ operacji wrzucenia prostokąta na stos.

O nieco ogólniejszej metodzie rozwiązania tego zadania można przeczytać w artykule Zliczamy puste prostokąty z miesięcznika Delta.