Hình chữ nhật giao nhau (DUTPC'21)

Xem PDF

Điểm: 500 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một lưới hình vuông kích thước \(10^9 * 10^9\) được chia làm các hình vuông nhỏ kích thước \(1 * 1\). Các hàng của lưới hình vuông đánh số từ \(1\) đến \(10^9\) từ trên xuống và các cột đánh số từ \(1\) đến \(10^9\) từ trái qua phải. Ô nằm trên giao của hàng \(i\) và cột \(j\) gọi là ô \((i,j)\).
\(n\) hình chữ nhật và có cạnh song song với lưới và nằm trong lưới hình vuông trên. Hình chữ nhật thứ \(i\) có góc trên bên trái là ô \((a_i,b_i)\) và ô ở góc dưới bên phải là ô \((c_i,d_i)\).

Hai hình chữ nhật được gọi là giao nhau nếu chúng có chung ít nhất một ô. Hãy đếm số lượng các cặp hình chữ nhật \((u,v)\) với \((1≤u<v≤n)\) mà hình chữ nhật thứ \(u\) và hình chữ nhật thứ \(v\) giao nhau.

Input

  • Dòng đầu chứa số nguyên \(T≤ 1000\) là số bộ dữ liệu.
  • Với mỗi bộ dữ liệu:
    • Dòng đầu chứa số nguyên \(n≤2 * 10^5\).
    • \(n\) dòng tiếp theo, dòng thứ \(i\) chứa bốn số nguyên \(a_i,b_i,c_i,d_i\) cách nhau bởi những dấu cách \((1≤a_i≤c_i≤10^9;1≤b_i≤d_i≤10^9 )\).
  • Tổng các giá trị \(n\) trong tất cả các test không vượt quá \(2 * 10^5\).

Output

  • In ra \(T\) dòng, ứng với \(T\) bộ dữ liệu, in ra số lượng các cặp hình chữ nhật \((u,v)\) với \((1≤u<v≤n)\) mà hình chữ nhật thứ \(u\) và hình chữ nhật thứ \(v\) giao nhau.

Example

Test 1

Input
2
2
1 1 2 2
2 2 3 4
3
2 1 4 4
4 2 5 5
1 4 4 6
Output
1
3
Note

Test ví dụ 1:

có 1 cặp hình giao nhau (1, 2).

Test ví dụ 2:

có 3 cặp hình giao nhau: (1, 2), (1, 3), (2, 3).


Bình luận

Không có bình luận nào.