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} = {H+1\choose2}\cdot{W+1\choose2}$, 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)$.
W tym podzadaniu zachodzi $h_1\le h_2\le\dots\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]$.
Dla $N\le10^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\neq 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)$.
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).
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.
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.