Ta sẽ sử dụng thuật toán sweep Line để giải bài này.

Với mỗi ~y~ từ ~1~ đến ~10^6~, ta sẽ cần tìm phần diện tích bị bao phủ bởi đúng ~k~ tờ giấy nằm ở độ cao ~y~. Xét những tờ giấy có tung độ ~\geq y~, ta sẽ sắp xếp chúng theo ~x~ không giảm và dễ dàng nhận ra diện tích bao phủ chính là phần được giao bởi tờ giấy thứ ~k~ và ~k+1~.

Để tìm được diện tích đó, ta có thể sử dụng cấu trúc dữ liệu std::multi_set và std::priority_queue để duy trì những tờ giấy có tung độ ~\geq y~. Ở đây ta duy trì ~1~ multi_set gồm ~k~ tọa độ có ~x~ lớn nhất, ~1~ priority_queue lưu những tọa độ còn lại. Khi đi lên ~y+1~, ta sẽ xóa những tờ giấy có tung độ là ~y~ trong multi_set và sẽ thêm những tọa độ mới từ priority_queue vào multi_set.

Code minh họa.

Ngoài ra ta có thể sử dụng cấu trúc dữ liệu Fenwick Tree kết hợp Two Pointer thay thế cho 2 cấu trúc dữ liệu trên với hằng số nhỏ hơn, tối ưu thời gian chạy.

Code minh họa.