Cho n hình chữ nhật song song với hai trục tọa độ. Hãy tính diện tích phần mặt phẳng được ít nhất một hình phủ.
Input
Dòng đầu chứa số nguyên n.
Mỗi trong n dòng tiếp theo chứa x1,y1,x2,y2 của hai góc đối, với x1<x2 và y1<y2.
Output
In diện tích hợp của các hình chữ nhật.
Constraints
1≤n≤105.
−106≤x1<x2≤106.
−106≤y1<y2≤106.
Vùng chồng nhau chỉ được tính một lần.
Scoring
Subtask 1 (50% số điểm): n≤8 và mọi tọa độ có trị tuyệt đối không quá 20.
Subtask 2 (50% số điểm): Không có giới hạn bổ sung.
Example
Test 1
Input
3
0 0 4 2
2 1 5 4
5 0 7 1
Output
17
Giải thích: Hai hình đầu có tổng diện tích 17 nhưng chồng nhau trên vùng diện tích 2, nên hợp của chúng có diện tích 15. Hình thứ ba chỉ chạm biên và đóng góp thêm 2.
Lời giải tóm tắt
Ý tưởng: Quét theo hoành độ; segment tree trên các khoảng tung độ duy trì tổng độ dài đang được phủ.
Ý tưởng: 1. Nén toàn bộ y1,y2; lá segment tree đại diện khoảng nguyên liên tục [Y_i,Y_{i+1}). 2. Tạo sự kiện (x1,+1,[y1,y2)) và (x2,-1,[y1,y2)). 3. Trước khi áp dụng nhóm sự kiện tại x, cộng (x-prevX)·coveredY vào diện tích. 4. Segment tree lưu coverCount và coveredLength; nếu coverCount>0, node được phủ toàn bộ, nếu không lấy tổng hai con.
Tính đúng đắn: 1. Trong dải x [prevX,x), không cạnh đứng nào xuất hiện, nên tập hình chữ nhật cắt dải đó là cố định. 2. Segment tree trả đúng độ dài hợp các khoảng y active nhờ quy tắc coverCount: node có count>0 được phủ hoàn toàn; count=0 thì hợp bằng tổng con. 3. Các dải x liên tiếp rời nhau và phủ toàn bộ hợp, do đó tổng width·coveredY bằng đúng diện tích hợp.
Độ phức tạp: O(n log n) thời gian, O(n) bộ nhớ.
Lưu ý cài đặt: Cập nhật lá theo khoảng giữa hai y, không phải điểm y.
Lưu ý cài đặt: Tính diện tích trước hay sau nhóm sự kiện tại x phải nhất quán.