← 返回题单
题单练习 树状数组
← 上一题 下一题 →

A6903 | 打招呼次数

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

数轴上有 $n$ 个人。第 $i$ 个人的起点是 $起点[i]=a_i$，终点是 $终点[i]=b_i$，并且一定有 $a_ib_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$ 个数都互不相同。

输出格式

对每个测试用例输出一行一个整数：总打招呼次数。

输入输出样例

输入 #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
C++ 编辑器
输入
输出