一道枚举题。
我们可以直接枚举那 \(2\) 个去掉的粉刷匠。先统计一下每个栅栏会被多少个粉刷匠刷到，然后枚举第一个被去掉的粉刷匠，然后计算剩下的粉刷匠会将每个栅栏刷到多少次，我们只需要看只能被刷 \(1\) 次的栅栏就行了。
接着处理一个前缀和数组，记录前 \(i\) 个栅栏中有多少个只能被 \(1\) 个粉刷匠刷到。然后枚举第二个被去掉的粉刷匠，然后通过前缀和用 \(O(1)\) 的时间复杂度查询，别忘了加上前面第一个粉刷匠去掉后没有被刷的栅栏的数量。最后取最小值，与 \(n\) 相减即是答案。
Code
#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
int n, q, minn = INF;
int l[5005], r[5005], cnt[5005], sum[5005];
signed main() {
ios :: sync_with_stdio(0);
cin >> n >> q;
for (int i = 1; i <= q; i++) {
cin >> l[i] >> r[i];
for (int j = l[i]; j <= r[i]; j++) cnt[j]++;
}
for (int i = 1; i <= q; i++) {
int x = 0;
for (int j = l[i]; j <= r[i]; j++) cnt[j]--;
for (int j = 1; j <= n; j++) {
sum[j] = sum[j - 1];
if (cnt[j] == 1) sum[j]++;
if (cnt[j] == 0) x++;
}
for (int j = 1; j <= q; j++) {
if (j == i) continue;
minn = min(minn, sum[r[j]] - sum[l[j] - 1] + x);
}
for (int j = l[i]; j <= r[i]; j++) cnt[j]++; // 别忘了要加回去继续枚举
}
cout << n - minn;
return 0;
}