{"code":"dutpc2e","name":"Hình chữ nhật giao nhau (DUTPC'21)","description":"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)$.\r\nCó $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)$.\r\n\r\nHai 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.\r\n\r\n<h4>Input</h4>\r\n\r\n - Dòng đầu chứa số nguyên $T≤ 1000$ là số bộ dữ liệu.\r\n - Với mỗi bộ dữ liệu:\r\n     - Dòng đầu chứa số nguyên $n≤2 * 10^5$.\r\n     - $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 )$.\r\n - Tổng các giá trị $n$ trong tất cả các test không vượt quá $2 * 10^5$.\r\n\r\n<h4>Output</h4>\r\n\r\n- 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.\r\n\r\n<h4>Example</h4>\r\n\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n\r\n        ```sample\r\n        2\r\n        2\r\n        1 1 2 2\r\n        2 2 3 4\r\n        3\r\n        2 1 4 4\r\n        4 2 5 5\r\n        1 4 4 6\r\n        ```\r\n\r\n    ???+ success \"Output\"\r\n\r\n        ```sample\r\n        1\r\n        3\r\n        ```\r\n        \r\n    ??? warning \"Note\"\r\n\r\n        Test ví dụ 1:\r\n\r\n        ![](https://i.imgur.com/93nOe1r.png)\r\n\r\n        có 1 cặp hình giao nhau (1, 2).\r\n\r\n        Test ví dụ 2: \r\n\r\n        ![](https://i.imgur.com/XM64WiZ.png)\r\n\r\n        có 3 cặp hình giao nhau: (1, 2), (1, 3), (2, 3).","points":500.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}