A6903. 打招呼次数
编程题
普及/提高-
知识点
题目描述
数轴上有 $n$ 个人。第 $i$ 个人的起点是 $起点[i]=a_i$，终点是 $终点[i]=b_i$，并且一定有 $a_i<b_i$。
所有人同时出发：
- 每秒向右走 $1$ 个单位；
- 走到自己的终点 $b_i$ 后就停在 $b_i$ 不再移动；
- 即使已经停下，也仍然可能和别人打招呼。
当两个人在某一时刻站在同一个点上（位置相同），他们就会互相打招呼 **一次**。
请你计算：总共会发生多少次打招呼。
所有人同时出发：
- 每秒向右走 $1$ 个单位；
- 走到自己的终点 $b_i$ 后就停在 $b_i$ 不再移动；
- 即使已经停下，也仍然可能和别人打招呼。
当两个人在某一时刻站在同一个点上（位置相同），他们就会互相打招呼 **一次**。
请你计算：总共会发生多少次打招呼。
输入格式
第一行一个整数 $t$，表示测试用例个数。
对每个测试用例：
- 第一行一个整数 $n$，表示人数。
- 接下来 $n$ 行，每行两个整数 $a_i\ b_i$，表示第 $i$ 个人的起点和终点。
保证：每个测试用例里，所有 $a_1,a_2,\dots,a_n,b_1,b_2,\dots,b_n$ 这 $2n$ 个数都互不相同。
对每个测试用例：
- 第一行一个整数 $n$，表示人数。
- 接下来 $n$ 行，每行两个整数 $a_i\ b_i$，表示第 $i$ 个人的起点和终点。
保证：每个测试用例里，所有 $a_1,a_2,\dots,a_n,b_1,b_2,\dots,b_n$ 这 $2n$ 个数都互不相同。
输出格式
对每个测试用例输出一行一个整数：总打招呼次数。
输入输出样例
输入 #1
5 2 2 3 1 4 6 2 6 3 9 4 5 1 8 7 10 -2 100 4 -10 10 -5 5 -12 12 -13 13 5 -4 9 -2 5 3 4 6 7 8 10 4 1 2 3 4 5 6 7 8
输出 #1
1 9 6 4 0
说明/提示
## 数据范围
- $1 \le t \le 10^4$
- $1 \le n \le 2\times10^5$
- $-10^9 \le a_i < b_i \le 10^9$
- 所有测试用例的 $n$ 之和 $\le 2\times10^5$
## 样例解释
- 第 1 组：两个人分别从 2→3、1→4 出发。
第一个人到 3 就停下；第二个人会在某一时刻走到 3。
所以他们会在点 3 相遇一次，总共打招呼 1 次。
- $1 \le t \le 10^4$
- $1 \le n \le 2\times10^5$
- $-10^9 \le a_i < b_i \le 10^9$
- 所有测试用例的 $n$ 之和 $\le 2\times10^5$
## 样例解释
- 第 1 组：两个人分别从 2→3、1→4 出发。
第一个人到 3 就停下；第二个人会在某一时刻走到 3。
所以他们会在点 3 相遇一次，总共打招呼 1 次。