[AGC040B] Two Contests
挺难的。首先有一个搞笑的想法，最长的一个区间单独划分一个集合，可扩展性不是很强。
猜一下最后可能是怎样的，我写了个按照 \(l\) 排序取前缀后缀，然后再结合上面的乱搞一下，只过了一半的点，不妙。
但是前缀后缀的思路还可以沿用，注意到写出来的式子里面有 \(l,r\) 两个参数，而且贡献很抽象，所以考虑转化一下贡献。
注意到所有 \(l\) 的最大值和所有 \(r\) 的最小值是特殊的两个量，我们可以利用这两个量具体地描绘贡献，假定这两个量不在同一个集合内，那么一个区间的两种贡献分别为 \(r - \max l + 1\) 和 \(\min r - l + 1\)。然后就是经典的排序处理。
剩下只需处理这两个量在同一个集合内的划分，很显然剩下就取最长的区间即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
namespace IO {
#define isdigit(x) (x >= '0' && x <= '9')
template<typename T>
inline void read(T &x) {
x = 0; char ch = getchar(); int f = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
if(f) x = -x;
}
template<typename T, typename... Rest>
inline void read(T &x, Rest&... rest) {
read(x), read(rest...);
}
template<typename T>
inline void write(T x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
#undef isdigit
}
using namespace IO;
constexpr int N = 1e5 + 10;
int n;
struct Itv {
int l, r, a, b;
}a[N];
int suf[N];
int main() {
read(n);
for(int i = 1; i <= n; ++i)
read(a[i].l, a[i].r);
int u = 0, v = 0, ans = 0;
a[0] = {0, 1000000000, 0, 0};
for(int i = 1; i <= n; ++i) {
if(a[i].l > a[u].l) u = i;
if(a[i].r < a[v].r) v = i;
}
int mx = a[u].l, mn = a[v].r;
for(int i = 1; i <= n; ++i)
ans = max(ans, a[i].r - a[i].l + 1 + max(0, mn - mx + 1));
for(int i = 1; i <= n; ++i)
a[i].a = max(a[i].r - mx + 1, 0), a[i].b = max(mn - a[i].l + 1, 0);
sort(a + 1, a + n + 1, [](Itv x, Itv y) {
return x.a > y.a;
});
suf[n + 1] = 1e9;
for(int i = n; i >= 1; --i)
suf[i] = min(suf[i + 1], a[i].b);
mn = 1e9;
for(int i = 1; i < n; ++i) {
mn = min(mn, a[i].a);
ans = max(ans, mn + suf[i + 1]);
}
printf("%d\n",ans);
return 0;
}