310007: CF1771B. Hossam and Friends
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Hossam and Friends
题意翻译
有 $t$ 组数据，每组数据中给出两个数 $n$ 和 $m$，和 $m$ 个数对 $(x_i, y_i)$。求有多少个数对 $(a, b)$ 满足 $1\le a \le b \le n$ ，且不存在一个$i$，使得$a \le x_i, y_i \le b$。题目描述
Hossam makes a big party, and he will invite his friends to the party. He has $ n $ friends numbered from $ 1 $ to $ n $ . They will be arranged in a queue as follows: $ 1, 2, 3, \ldots, n $ . Hossam has a list of $ m $ pairs of his friends that don't know each other. Any pair not present in this list are friends. A subsegment of the queue starting from the friend $ a $ and ending at the friend $ b $ is $ [a, a + 1, a + 2, \ldots, b] $ . A subsegment of the queue is called good when all pairs of that segment are friends. Hossam wants to know how many pairs $ (a, b) $ there are ( $ 1 \le a \le b \le n $ ), such that the subsegment starting from the friend $ a $ and ending at the friend $ b $ is good.输入输出格式
输入格式
The input consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 2 \cdot 10^4 $ ), the number of test cases. Description of the test cases follows. The first line of each test case contains two integer numbers $ n $ and $ m $ ( $ 2 \le n \le 10^5 $ , $ 0 \le m \le 10^5 $ ) representing the number of friends and the number of pairs, respectively. The $ i $ -th of the next $ m $ lines contains two integers $ x_i $ and $ y_i $ ( $ 1 \le x_i, y_i\le n $ , $ x_i \neq y_i $ ) representing a pair of Hossam's friends that don't know each other. Note that pairs can be repeated. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ , and the sum of $ m $ over all test cases does not exceed $ 10^5 $ .
输出格式
For each test case print an integer — the number of good subsegments.
输入输出样例
输入样例 #1
2
3 2
1 3
2 3
4 2
1 2
2 3输出样例 #1
4
5说明
In the first example, the answer is $ 4 $ . The good subsegments are: \[1\] \[2\] \[3\] \[1, 2\] In the second example, the answer is $ 5 $ . The good subsegments are: \[1\] \[2\] \[3\] \[4\] \[3, 4\]Input
题意翻译
有 $t$ 组数据，每组数据中给出两个数 $n$ 和 $m$，和 $m$ 个数对 $(x_i, y_i)$。求有多少个数对 $(a, b)$ 满足 $1\le a \le b \le n$ ，且不存在一个$i$，使得$a \le x_i, y_i \le b$。Output
**题目大意：**
Hossam举办了一个大型派对，并邀请了他的朋友们参加。他有n个朋友，编号从1到n。他们将会按照1, 2, 3, ... n的顺序排队。Hossam有一张列表，上面列出了m对不认识彼此的朋友。任何未出现在列表中的朋友对都是朋友。
一个从朋友a开始到朋友b结束的队伍段是[a, a+1, a+2, ..., b]。当队伍段中的所有朋友对都是朋友时，该队伍段被称为好的。Hossam想知道有多少对(a, b)（1≤a≤b≤n），使得从朋友a开始到朋友b结束的队伍段是好的。
**输入输出数据格式：**
- **输入格式：**
输入包含多个测试用例。第一行包含一个整数t（1≤t≤2×10^4），表示测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含两个整数n和m（2≤n≤10^5，0≤m≤10^5），分别表示朋友数量和配对数量。
接下来的m行中的第i行包含两个整数x_i和y_i（1≤x_i,y_i≤n，x_i≠y_i），表示一对不认识彼此的Hossam的朋友。
注意，配对可能会重复。
保证所有测试用例的n之和不超过10^5，m之和不超过10^5。
- **输出格式：**
对于每个测试用例，打印一个整数——好的队伍段的数量。
**输入输出样例：**
- **输入样例 #1：**
```
2
3 2
1 3
2 3
4 2
1 2
2 3
```
- **输出样例 #1：**
```
4
5
```**题目大意：** Hossam举办了一个大型派对，并邀请了他的朋友们参加。他有n个朋友，编号从1到n。他们将会按照1, 2, 3, ... n的顺序排队。Hossam有一张列表，上面列出了m对不认识彼此的朋友。任何未出现在列表中的朋友对都是朋友。 一个从朋友a开始到朋友b结束的队伍段是[a, a+1, a+2, ..., b]。当队伍段中的所有朋友对都是朋友时，该队伍段被称为好的。Hossam想知道有多少对(a, b)（1≤a≤b≤n），使得从朋友a开始到朋友b结束的队伍段是好的。 **输入输出数据格式：** - **输入格式：** 输入包含多个测试用例。第一行包含一个整数t（1≤t≤2×10^4），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数n和m（2≤n≤10^5，0≤m≤10^5），分别表示朋友数量和配对数量。 接下来的m行中的第i行包含两个整数x_i和y_i（1≤x_i,y_i≤n，x_i≠y_i），表示一对不认识彼此的Hossam的朋友。 注意，配对可能会重复。 保证所有测试用例的n之和不超过10^5，m之和不超过10^5。 - **输出格式：** 对于每个测试用例，打印一个整数——好的队伍段的数量。 **输入输出样例：** - **输入样例 #1：** ``` 2 3 2 1 3 2 3 4 2 1 2 2 3 ``` - **输出样例 #1：** ``` 4 5 ```
Hossam举办了一个大型派对，并邀请了他的朋友们参加。他有n个朋友，编号从1到n。他们将会按照1, 2, 3, ... n的顺序排队。Hossam有一张列表，上面列出了m对不认识彼此的朋友。任何未出现在列表中的朋友对都是朋友。
一个从朋友a开始到朋友b结束的队伍段是[a, a+1, a+2, ..., b]。当队伍段中的所有朋友对都是朋友时，该队伍段被称为好的。Hossam想知道有多少对(a, b)（1≤a≤b≤n），使得从朋友a开始到朋友b结束的队伍段是好的。
**输入输出数据格式：**
- **输入格式：**
输入包含多个测试用例。第一行包含一个整数t（1≤t≤2×10^4），表示测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含两个整数n和m（2≤n≤10^5，0≤m≤10^5），分别表示朋友数量和配对数量。
接下来的m行中的第i行包含两个整数x_i和y_i（1≤x_i,y_i≤n，x_i≠y_i），表示一对不认识彼此的Hossam的朋友。
注意，配对可能会重复。
保证所有测试用例的n之和不超过10^5，m之和不超过10^5。
- **输出格式：**
对于每个测试用例，打印一个整数——好的队伍段的数量。
**输入输出样例：**
- **输入样例 #1：**
```
2
3 2
1 3
2 3
4 2
1 2
2 3
```
- **输出样例 #1：**
```
4
5
```**题目大意：** Hossam举办了一个大型派对，并邀请了他的朋友们参加。他有n个朋友，编号从1到n。他们将会按照1, 2, 3, ... n的顺序排队。Hossam有一张列表，上面列出了m对不认识彼此的朋友。任何未出现在列表中的朋友对都是朋友。 一个从朋友a开始到朋友b结束的队伍段是[a, a+1, a+2, ..., b]。当队伍段中的所有朋友对都是朋友时，该队伍段被称为好的。Hossam想知道有多少对(a, b)（1≤a≤b≤n），使得从朋友a开始到朋友b结束的队伍段是好的。 **输入输出数据格式：** - **输入格式：** 输入包含多个测试用例。第一行包含一个整数t（1≤t≤2×10^4），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数n和m（2≤n≤10^5，0≤m≤10^5），分别表示朋友数量和配对数量。 接下来的m行中的第i行包含两个整数x_i和y_i（1≤x_i,y_i≤n，x_i≠y_i），表示一对不认识彼此的Hossam的朋友。 注意，配对可能会重复。 保证所有测试用例的n之和不超过10^5，m之和不超过10^5。 - **输出格式：** 对于每个测试用例，打印一个整数——好的队伍段的数量。 **输入输出样例：** - **输入样例 #1：** ``` 2 3 2 1 3 2 3 4 2 1 2 2 3 ``` - **输出样例 #1：** ``` 4 5 ```