AREA - Diện tích hình chữ nhật

Problem

https://vn.spoj.com/problems/AREA

https://oj.vnoi.info/problem/AREA

Trên mặt phẳng toạ độ người ta vẽ ra N hình chữ nhật. Hãy tính diện tích che phủ bởi N hình chữ nhật này, biết rằng N hình chữ nhật này song song với 2 trục Ox và Oy .

Input

Dòng 1 : số nguyên N ( 1 ≤ N ≤ 10000 ) .
N dòng tiếp theo , mỗi dòng gồm 4 số nguyên x1 , y1 , x2 , y2 tương ứng là toạ độ góc trái dưới và góc phải trên của hình chữ nhật thứ i.( 0 ≤ x1 ≤ x2 ≤ 30000 , 0 ≤ y1≤ y2 ≤ 30000 ) .

Output

Gồm 1 dòng ghi ra diện tích phủ bởi N hình chữ nhật

Example

Input
2
10 10 20 20
15 15 25 30

Output
225 

Tutorial

Trước hết chia mỗi hình chữ nhật (HCN) thành hai đường thẳng thẳng đứng tương ứng với hai tọa độ x, do đó 1 HCN sẽ có một cạnh mở (bắt đầu 1 HCN mới) và 1 cạnh đóng (kết thúc một HCN). Sau đó ta sort danh sách 2n cạnh này theo thứ tự tăng dần trục x. Khi đó ta lần lượt tính diện tích trên mỗi khoảng của x, bắt đầu tại x = 0. Khi đi qua một khoảng, ta cộng thêm lượng [x(trước) - x(sau)] * (tổng chiều dài trên khoảng x này hiện tại có hình chữ nhật) vào ans. Khi x(trước) = x(sau) thì nó chỉ có nhiệm vụ cập nhật lại chiều dài trên khoảng x này. Do đó, khi sort ta ưu tiên cạnh đóng trước, kết thúc những HCN để tránh cộng dư diện tích.

Bây giờ, vấn đề đặt ra là làm sao tính được tổng chiều dài trên 1 khoảng x như vậy ? Ta nhận thấy rằng mỗi lần qua 1 khoảng thì ta có hai thao tác trên trục y, thứ nhất là lấy tổng chiều dài, thứ hai là cập nhật thêm hoặc xóa trên một đoạn, cùng với 0 <= y <= 30000 khiến ta liên tưởng đến Segment Tree.

Mỗi nút Segment Tree lúc này lưu hai biến cnt và len lần lượt có ý nghĩa là số lượng HCN phủ cả đoạn này hiện tại và tổng chiều dài bị các HCN chiếm giữ hiện tại (nếu cnt > 0 thì tất nhiên là cả chiều dài đoạn này, còn không thì là tổng chiều dài từng phần của các HCN khác).

Và ở đây do là trục tọa độ, để dễ dàng hơn ta chuyển thành đoạn trên trục, như (0->1) = 1; (1->2) = 2; … do đó với một HCN có hai thông số y1, y2 (y1 <= y2) thì nó sẽ bắt đầu từ đoạn y1 đến đoạn y2-1, trong trường hợp y1 == y2 thì ta không làm gì hết.

Lúc này, với thao tác lấy tổng chiều dài trên cả trục y thì ta chỉ cần gọi t[1].len. Còn với thao tác update trên một đoạn, ta cộng số lượng HCN vào nút (1, với mở hoặc -1, nếu như là đóng). Với một nút có đoạn nằm trong đoạn update, thì nếu như đoạn này là mở thì toàn bộ đoạn này được phủ nên t[k].len = r-l+1, trong trường hợp ngược lại, nếu đoạn này không còn HCN phủ cả đoạn nữa (ứng với trường hợp là cạnh đóng) thì ta truy xuất đến hai nút con để lấy tổng chiều dài các HCN khác (lưu ý là nếu truy xuất đến nút lá, l == r, thì t[k].len = 0 do không còn HCN nào nữa).

Việc combine hai nút chỉ là kiểm tra xem còn HCN hay không, nếu không thì lấy hai nút lá.

Submission

AREA.cpp

Tutorial SPOJ