Observation of Combining Rectangles

Let’s consider combining rectangles consecutively. Starting from \((h_1, w_1)\), we combine \((h_2, w_2)\), and then continue to combine \((h_3, w_3)\). At this time, we consider the condition that if \((h_2, w_2)\) can be combined vertically/horizontally, then \((h_3, w_3)\) can also be combined vertically/horizontally.

For example, when \(h_2 = h_3\), if \((h_2, w_2)\) can be combined horizontally, then \((h_3, w_3)\) can also be combined horizontally. Similarly, when \(w_2 = w_3\), if \((h_2, w_2)\) can be combined vertically, then \((h_3, w_3)\) can also be combined vertically.

Let’s consider combinations with different orientations. Here, it is not always clear whether the condition holds only from \((h_2, w_2)\) and \((h_3, w_3)\). However, the area of the rectangle that \((h_2, w_2)\) combines with is uniquely determined.

For example, if \((h_2, w_2)\) can be combined vertically, then \((h_3, w_3)\) can be combined horizontally if and only if the area of \((h_1, w_1)\) is \((h_3 - h_2)w_2\).

Correspondence to Graph and Counting

Let’s count the number of pairs \((l, r)\) that satisfy the condition. When \(l\) is fixed, whether \((l, r)\) satisfies the condition has monotonicity with respect to \(r\). Hence, we fix \(l\).

By fixing \(l\), for the orientation of the combination of two consecutive rectangles, we can determine whether the latter can be combined if the former can be combined. Let’s represent this information in a graph with \(2 \times N\) vertices.

For \(i = 1, 2, \dots, N\), let vertex \(i\) represent that \((H_i, W_i)\) can be combined vertically, and vertex \(N + i\) represent that \((H_i, W_i)\) can be combined horizontally.

For \(i = 2, 3, \dots, N\), do the following:

• If, assuming that \((H_{i-1}, W_{i-1})\) can be combined vertically, \((H_i, W_i)\) can be combined vertically, then span an edge between vertices \(i-1\) and \(i\).
• If, assuming that \((H_{i-1}, W_{i-1})\) can be combined vertically, \((H_i, W_i)\) can be combined horizontally, then span an edge between vertices \(i-1\) and \(N + i\).
• If, assuming that \((H_{i-1}, W_{i-1})\) can be combined horizontally, \((H_i, W_i)\) can be combined vertically, then span an edge between vertices \(N + i - 1\) and \(i\).
• If, assuming that \((H_{i-1}, W_{i-1})\) can be combined horizontally, \((H_i, W_i)\) can be combined horizontally, then span an edge between vertices \(N + i - 1\) and \(N + i\).

For convenience, assume that \((H_l, W_l)\) can be combined both horizontally and vertically. Then, \((l, r)\) satisfies the condition if and only if either vertex \(l\) or \(N + l\) is connected to either vertex \(r\) or \(N + r\).

Edges corresponding to combinations with different orientations will be spanned for at most one \(l\). On the other hand, edges corresponding to combinations with the same orientation will be spanned for any \(l\) if they are spanned.

Represent the edges of the graph as a \(2 \times 2\) matrix and load it on a segment tree. By performing binary search on the segment tree to find the maximum \(r\) that satisfies the condition, and updating the graph with segment tree updates, we can process all \(l\) in \(\mathrm{O}(N \log N)\) time complexity.