题解 P2352 【队爷的新书】
wtxy2006
·
·
题解
Describe:
### Solution:
主要思路：离散化，差分。
注意到点最大能到 $1e9$，但是最多只有 $1e5$ 个点，所以使用离散化。
然后统计每个点被覆盖的次数，显然这是一个区间加法问题，差分加前缀和就行了。
最后在枚举选这个点时，$value$ 为多少，取最大值即可。
### Code:
附上丑陋的代码~~
```cpp
// P2352 队爷的新书
#include <algorithm>
#include <cstdio>
#include <iostream>
#define int long long
#define MN 1000005
using namespace std;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x * f;
}
int n, a[MN], b[MN], f[MN * 2], cnt = 0, s[MN * 2], ans;
signed main() {
n = read();
for (int i = 0; i < n; i++)
a[i] = f[cnt++] = read(), f[cnt++] = b[i] = read();
sort(f, f + cnt), cnt = unique(f, f + cnt) - f;
for (int i = 0; i < n; i++)
a[i] = lower_bound(f, f + cnt, a[i]) - f,
b[i] = lower_bound(f, f + cnt, b[i]) - f;
for (int i = 0; i < n; i++) {
s[a[i]]++, s[b[i] + 1]--;
}
for (int i = 1; i < cnt + 1; i++) s[i] += s[i - 1];
int now = 0;
for (int i = 1; i < cnt + 1; i++) {
if (now == s[i]) continue;
ans = max(ans, s[i - 1] * f[i - 1]);
}
printf("%lld", ans);
return 0;
}
```