题解 CF1320C 【World of Darkraft: Battle for Azathoth】
xht
2020-03-03 15:12:28
以攻击值为横坐标，防御值为纵坐标，问题变成：
- 平面上有一些点，每个点都有一个权值，每个横纵坐标都有一个代价。
- 你要选择一个横坐标和一个纵坐标，使**严格在它们和坐标轴构成的矩形内的点的权值和**减去**这两个坐标的代价**最大。
考虑扫描线，在当前横坐标选择每个纵坐标的贡献，每次取最大贡献减去当前横坐标的代价。
加入一个点相当于一个区间加的操作，询问相当于全局 $\max$ 的操作，因此线段树维护即可。
由于值域只有 $10^6$，因此甚至不用离散化。
```cpp
const int N = 2e5 + 7, M = 1e6 + 1;
const ll inf = 1e18;
int n, m, k;
ll a[M], b[M];
vector<pi> p[M];
struct T {
int l, r;
ll x, z;
} t[M*5];
void build(int p, int l, int r) {
t[p].l = l, t[p].r = r;
if (l == r) return t[p].x = -b[l], void();
build(ls, l, md), build(rs, md + 1, r);
t[p].x = max(t[ls].x, t[rs].x);
}
void spd(int p) {
if (t[p].z) {
t[ls].x += t[p].z;
t[ls].z += t[p].z;
t[rs].x += t[p].z;
t[rs].z += t[p].z;
t[p].z = 0;
}
}
void add(int p, int l, int r, ll k) {
if (t[p].l >= l && t[p].r <= r) return t[p].x += k, t[p].z += k, void();
spd(p);
if (l <= md) add(ls, l, r, k);
if (r > md) add(rs, l, r, k);
t[p].x = max(t[ls].x, t[rs].x);
}
int main() {
rd(n), rd(m), rd(k);
for (int i = 1; i < M; i++) a[i] = b[i] = inf;
for (int i = 1, x, y; i <= n; i++)
rd(x), rd(y), a[x] = min(a[x], 1ll * y);
for (int i = 1, x, y; i <= m; i++)
rd(x), rd(y), b[x] = min(b[x], 1ll * y);
for (int i = 1, x, y, z; i <= k; i++)
rd(x), rd(y), rd(z), p[x].pb(mp(y, z));
build(1, 1, M - 1);
ll ans = -inf;
for (int i = 1; i < M; i++) {
ans = max(ans, t[1].x - a[i]);
for (pi o : p[i]) if (o.fi != M - 1) add(1, o.fi + 1, M, o.se);
}
print(ans);
return 0;
}
```