Bài này có thể được giải bằng nhiều cách. Dưới đây là cách giải bằng việc sử dụng sweep line và DSU.

Ta có thể coi mỗi hình chữ nhật là một bộ số gồm bốn giá trị (~x_1, y_1, x_2, y_2~) với ~x_1 = X~, ~y_1 = Y~, ~x_2 = X + D~ và ~y_2 = Y + C~.

Cách làm này khá giống bài AREA trên VNOJ:

• Rời rạc hóa các tọa độ ~y_1~ và ~y_2~ của hình chữ nhật thành tọa độ tương ứng là ~y_1'~ và ~y_2'~.

• Quét lần lượt các đường theo ~x~ tăng dần, kết hợp với DSU để "nối" các hình chữ nhật trong cùng một vùng với nhau.

Tuy nhiên, bài này vẫn có một số khác biệt nhất định:

• Các hình chữ nhật không chồng lên nhau nên diện tích của một vùng chính là tổng diện tích của tất cả hình chữ nhật trong vùng đó.

• Dễ dàng nhận thấy ~y_2' - y_1' \le y_2 - y_1 = C \le 500~, nên ta có thể chạy trâu từng điểm trong đoạn [~y_1', y_2'~] thay vì sử dụng segment tree và lazy update để cài đặt dễ dàng hơn.

Độ phức tạp: ~O(NlogN + N \times D)~.