题目大意
你有$n$个区间$[l_i, r_i]$， 你要恰好删掉一个区间，使得剩下的$n-1$个区间的并的总和最多
eg. [1,2], [3,5], [3,7]的并是[1,2], [3,7]
题目分析
首先我们将给定的区间进行离散化
由于区间端点相邻的区间并不算相交，所以离散化时要进行特殊处理$(x=x*2-1)$
然后本题就变成了这样一个问题:
1.对于所有$[l_i, r_i]$, 把对应区间的数值$a_i$全部加上1，并统计此时所有区间并的个数$num$
2.对于每个$[l_i, r_i]$, 求出该区间内满足$a_i=1$的连续段个数，并统计最大值$ans$
那么，$ans+num$即为答案
对于步骤$1$，可以用差分求出；对于步骤$2$， 可以用前缀和求出（注意特判开头和结尾相等的情况）
代码
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include <bits/stdc++.h>
#define R register
#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)
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;
}
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch > '9' || ch < '0')
{
if (ch == '-')
f = 0;
ch = getchar();
}
while (ch <= '9' && ch >= '0')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return f ? x : (-x);
}
int main()
{
int T = read();
while (T--)
{
n = read(), cnt = 0;
for (int i = 1; i <= n; i++)
l[i] = read(), r[i] = read();
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);
}
printf("%d\n", num + ans);
for (int i = 0; i <= cnt * 2; i++)
a[i] = s[i] = 0;
}
return 0;
}
|