题解 CF1320C 【World of Darkraft: Battle for Azathoth】
皎月半洒花
2020-03-03 07:01:19
> 给定一系列有代价的装备，第一种提供 $x$ 值，第二种提供 $y$ 值。给出一些怪兽，如果怪兽的 $x_i$ 和 $y_i$ 都小于选定的 $x$ 和 $y$ ，那么会有 $z_i$ 的奖励。最大化收益。
>
> $1\leq n\leq 2\times 10^5$ 。
一个比较自然的想法是排序之后枚举一维坐标，然后去算另一维。然而另一维并不具备单调性。考虑对于一个确切的 $x$ ，如何选择一个最优的 $y$ 取到最大值。考虑快速查找一个 $y$ 的最优值，需要快速计算当前 $y$ 可以提供击败哪些怪兽的贡献。
考虑将询问按照 $x$ 排序，就转化和成了一个二维扫描线问题。考虑用线段树维护每个 $y$ 值处的最大值。枚举第一种装备，每次用双指针扫到当前的 $x_i$，提前用线段树进行 $y$ 坐标的后缀加计算贡献。最后答案就是所有 $y$ 的最大值减去使用当前 $x$ 的代价。
感觉现在语言越来越苍白无力，还是代码比较容易说明道理。
```cpp
#define LL long long
#define lowb lower_bound
#define uppb upper_bound
const int N = 200010 ;
const int S = 1000000101 ;
LL ans ;
int len ;
int tmp[N] ;
int n, m, k ;
struct arm{
int x ;
int c ;
bool operator < (const arm & t)
const { return t.x == x ? t.c > c : t.x > x ; }
}a[N], b[N] ;
struct monster{
int x, y, v ;
bool operator < (const monster & t)
const { return t.y == y ? t.x > x : t.y > y ; }
}base[N] ;
LL s[N * 3] ;
LL tag[N * 3] ;
void _up(int x){
s[x] = max(s[x << 1], s[x << 1 | 1]) ;
}
void _down(int x){
if (tag[x]){
s[x << 1] += tag[x] ;
s[x << 1 | 1] += tag[x] ;
tag[x << 1] += tag[x] ;
tag[x << 1 | 1] += tag[x] ;
}
tag[x] = 0 ;
}
void chkmax(LL& a, int b){
a = b > a ? b : a ; return ;
}
void update(int rt, int l, int r, int v, int p){
if (l == r)
return chkmax(s[rt], v) ;
int mid = (l + r) >> 1 ;
if (p <= mid) update(rt << 1, l, mid, v, p) ;
else update (rt << 1 | 1, mid + 1, r, v, p) ;
}
void update(int rt, int l, int r, int v, int ul, int ur){
if (ul <= l && r <= ur){
return s[rt] += v, tag[rt] += v, void() ;
}
int mid = (l + r) >> 1 ; _down(rt) ;
if (ul <= mid) update(rt << 1, l, mid, v, ul, ur) ;
if (ur > mid) update(rt << 1 | 1, mid + 1, r, v, ul, ur) ;
_up(rt) ;
}
int main(){
cin >> n >> m >> k ;
memset(s, -63, sizeof(s)) ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%d%d", &a[i].x, &a[i].c) ;
for (int i = 1 ; i <= m ; ++ i)
scanf("%d%d", &b[i].x, &b[i].c) ;
sort(b + 1, b + m + 1) ;
for (int i = 1 ; i <= k ; ++ i)
scanf("%d%d%d", &base[i].x, &base[i].y, &base[i].v) ;
sort(base + 1, base + k + 1) ;
for (int i = 1 ; i <= n ; ++ i) tmp[i] = a[i].x ;
sort(tmp + 1, tmp + n + 1) ;
len = unique(tmp + 1, tmp + n + 1) - (tmp + 1) ;
for (int i = 1 ; i <= k ; ++ i)
base[i].x = uppb(tmp + 1, tmp + len + 1, base[i].x) - tmp ;
for (int i = 1 ; i <= n ; ++ i){
a[i].x = lowb(tmp + 1, tmp + len + 1, a[i].x) - tmp ;
update(1, 1, len, - a[i].c, a[i].x) ;
}
//cout <<s[1]<<endl;//, cout << base[i].y<<endl;
int now = 1 ; ans = - (S + S) ;
for (int i = 1 ; i <= m ; ++ i){
//cout << b[i].x << endl ;
while (now <= k && base[now].y < b[i].x)
update(1, 1, len, base[now].v, base[now].x, len), ++ now ;
//cout << now << endl, cout << s[1] << " ---------- " << endl ;
ans = max(ans, s[1] - b[i].c) ;
}
cout << ans << endl ; return 0 ;
}
```