CF1285E-Delete a Segment

题目:

题目描述:

There are $ n $ segments on a $ Ox $ axis $ [l_1, r_1] $ , $ [l_2, r_2] $ , …, $ [l_n, r_n] $ . Segment $ [l, r] $ covers all points from $ l $ to $ r $ inclusive, so all $ x $ such that $ l \le x \le r $ .

Segments can be placed arbitrarily — be inside each other, coincide and so on. Segments can degenerate into points, that is $ l_i=r_i $ is possible.

Union of the set of segments is such a set of segments which covers exactly the same set of points as the original set. For example:

• if $ n=3 $ and there are segments $ [3, 6] $ , $ [100, 100] $ , $ [5, 8] $ then their union is $ 2 $ segments: $ [3, 8] $ and $ [100, 100] $ ;
• if $ n=5 $ and there are segments $ [1, 2] $ , $ [2, 3] $ , $ [4, 5] $ , $ [4, 6] $ , $ [6, 6] $ then their union is $ 2 $ segments: $ [1, 3] $ and $ [4, 6] $ .

Obviously, union is a set of pairwise non-intersecting segments.

You are asked to erase exactly one segment of the given $ n $ so that the number of segments in the union of the rest $ n-1 $ segments is maximum possible.

For example, if $ n=4 $ and there are segments $ [1, 4] $ , $ [2, 3] $ , $ [3, 6] $ , $ [5, 7] $ , then:

• erasing the first segment will lead to $ [2, 3] $ , $ [3, 6] $ , $ [5, 7] $ remaining, which have $ 1 $ segment in their union;
• erasing the second segment will lead to $ [1, 4] $ , $ [3, 6] $ , $ [5, 7] $ remaining, which have $ 1 $ segment in their union;
• erasing the third segment will lead to $ [1, 4] $ , $ [2, 3] $ , $ [5, 7] $ remaining, which have $ 2 $ segments in their union;
• erasing the fourth segment will lead to $ [1, 4] $ , $ [2, 3] $ , $ [3, 6] $ remaining, which have $ 1 $ segment in their union.

Thus, you are required to erase the third segment to get answer $ 2 $ .

Write a program that will find the maximum number of segments in the union of $ n-1 $ segments if you erase any of the given $ n $ segments.

Note that if there are multiple equal segments in the given set, then you can erase only one of them anyway. So the set after erasing will have exactly $ n-1 $ segments.

输入格式:

The first line contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases in the test. Then the descriptions of $ t $ test cases follow.

The first of each test case contains a single integer $ n $ ( $ 2 \le n \le 2\cdot10^5 $ ) — the number of segments in the given set. Then $ n $ lines follow, each contains a description of a segment — a pair of integers $ l_i $ , $ r_i $ ( $ -10^9 \le l_i \le r_i \le 10^9 $ ), where $ l_i $ and $ r_i $ are the coordinates of the left and right borders of the $ i $ -th segment, respectively.

The segments are given in an arbitrary order.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot10^5 $ .

输出格式:

Print $ t $ integers — the answers to the $ t $ given test cases in the order of input. The answer is the maximum number of segments in the union of $ n-1 $ segments if you erase any of the given $ n $ segments.

样例:

样例输入1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

3
4
1 4
2 3
3 6
5 7
3
5 5
5 5
5 5
6
3 3
1 1
5 5
1 5
2 2
4 4

样例输出1:

1
2
3

2
1
5

思路:

实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include "ybwhead/ios.h"

const int MaxN = 1e6 + 10;

std::map<int, int> m1, m2;
int n, cnt, l[MaxN], r[MaxN], a[MaxN], s[MaxN];

inline void prework()
{
    m1.clear(), m2.clear();
    for (int i = 1; i <= n; i++)
        m1[l[i]] = m1[r[i]] = 1;
    cnt = 0;
    for (std::map<int, int>::iterator it = m1.begin(); it != m1.end(); it++)
        m2[it->first] = ++cnt;
    for (int i = 1; i <= n; i++)
        l[i] = m2[l[i]] * 2 - 1, r[i] = m2[r[i]] * 2 - 1;
}

int main()
{
    int T;
    yin >> T;
    while (T--)
    {
        yin >> n;
        cnt = 0;
        for (int i = 1; i <= n; i++)
            yin >> l[i] >> r[i];
        prework(), cnt = cnt * 2 - 1;
        for (int i = 1; i <= n; i++)
            a[l[i]]++, a[r[i] + 1]--;
        for (int i = 1; i <= cnt; i++)
            a[i] += a[i - 1];
        int num = 0, ans = -1000000;
        for (int i = 1; i <= cnt; i++)
        {
            s[i] = s[i - 1];
            num += (a[i] && !a[i - 1]);
            if (a[i] > 1 && a[i - 1] <= 1)
                ++s[i];
        }
        for (int i = 1; i <= n; i++)
        {
            int cur = s[r[i]] - s[l[i] - 1] + ((a[l[i]] > 1) && (a[l[i] - 1] > 1)) - 1;
            ans = std::max(ans, cur);
        }
        yout << num + ans << endl;
        for (int i = 0; i <= cnt * 2; i++)
            a[i] = s[i] = 0;
    }
    return 0;
}