A16168. Medium Design
编程题
普及/提高-
知识点
题目描述
The array $a_1, a_2, \ldots, a_m$ is initially filled with zeroes. You are given $n$ pairwise distinct segments $1 \le l_i \le r_i \le m$ . You have to select an arbitrary subset of these segments (in particular, you may select an empty set). Next, you do the following:
- For each $i = 1, 2, \ldots, n$ , if the segment $(l_i, r_i)$ has been selected to the subset, then for each index $l_i \le j \le r_i$ you increase $a_j$ by $1$ (i. e. $a_j$ is replaced by $a_j + 1$ ). If the segment $(l_i, r_i)$ has not been selected, the array does not change.
- Next (after processing all values of $i = 1, 2, \ldots, n$ ), you compute $\max(a)$ as the maximum value among all elements of $a$ . Analogously, compute $\min(a)$ as the minimum value.
- Finally, the cost of the selected subset of segments is declared as $\max(a) - \min(a)$ .
Please, find the maximum cost among all subsets of segments.
- For each $i = 1, 2, \ldots, n$ , if the segment $(l_i, r_i)$ has been selected to the subset, then for each index $l_i \le j \le r_i$ you increase $a_j$ by $1$ (i. e. $a_j$ is replaced by $a_j + 1$ ). If the segment $(l_i, r_i)$ has not been selected, the array does not change.
- Next (after processing all values of $i = 1, 2, \ldots, n$ ), you compute $\max(a)$ as the maximum value among all elements of $a$ . Analogously, compute $\min(a)$ as the minimum value.
- Finally, the cost of the selected subset of segments is declared as $\max(a) - \min(a)$ .
Please, find the maximum cost among all subsets of segments.
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \le t \le 10^4$ ). The description of the test cases follows.
The first line of each test case contains two integers $n$ and $m$ ( $1 \le n \le 10^5$ , $1 \le m \le 10^9$ ) — the number of segments and the length of the array.
The following $n$ lines of each test case describe the segments. The $i$ -th of these lines contains two integers $l_i$ and $r_i$ ( $1 \le l_i \le r_i \le m$ ). It is guaranteed that the segments are pairwise distinct.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .
The first line of each test case contains two integers $n$ and $m$ ( $1 \le n \le 10^5$ , $1 \le m \le 10^9$ ) — the number of segments and the length of the array.
The following $n$ lines of each test case describe the segments. The $i$ -th of these lines contains two integers $l_i$ and $r_i$ ( $1 \le l_i \le r_i \le m$ ). It is guaranteed that the segments are pairwise distinct.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .
输出格式
For each test case, output the maximum cost among all subsets of the given set of segments.
输入输出样例
输入 #1
6 1 3 2 2 3 8 2 4 3 5 4 6 6 3 1 1 1 2 1 3 2 2 2 3 3 3 7 6 2 2 1 6 1 2 5 6 1 5 4 4 3 6 6 27 6 26 5 17 2 3 20 21 1 22 12 24 4 1000000000 2 999999999 3 1000000000 123456789 987654321 9274 123456789
输出 #1
1 3 2 3 4 4
说明/提示
In the first test case, there is only one segment available. If we do not select it, then the array will be $a = [0, 0, 0]$ , and the cost of such (empty) subset of segments will be $0$ . If, however, we select the only segment, the array will be $a = [0, 1, 0]$ , and the cost will be $1 - 0 = 1$ .
In the second test case, we can select all the segments: the array will be $a = [0, 1, 2, 3, 2, 1, 0, 0]$ in this case. The cost will be $3 - 0 = 3$ .
In the second test case, we can select all the segments: the array will be $a = [0, 1, 2, 3, 2, 1, 0, 0]$ in this case. The cost will be $3 - 0 = 3$ .