Hi,

I’m trying the CSES problem Area of Rectangles.

• We are given n rectangles with coordinates (x1, y1, x2, y2).
• The task is to find the total area of their union.
• Constraints go up to 10^5 rectangles and coordinates up to 10^6.

I saw in some discussions that this requires a sweep line algorithm with a segment tree/interval tree, but I don’t know sweep line yet.

Could someone please explain: 1. What sweep line means in this context (step by step)? 2. How the rectangles are turned into events for sweeping? 3. What exactly the segment tree/interval tree is keeping track of during the sweep? 4. How this avoids double-counting overlapping areas?

I’m not asking for full code — I want to understand the idea from the basics, since I haven’t studied sweep line before.

Thanks a lot!