Description
给定一系列有代价的装备，第一种提供 $x$ 值，第二种提供 $y$ 值。给出一些怪兽，如果怪兽的 $x_i$ 和 $y_i$ 都小于选定的 $x$ 和 $y$ ，那么会有 $z_i$ 的奖励。最大化收益。
Solution
Algorithm 1
枚举武器 $i$，防具 $j$，再遍历每一个怪物，算出总奖励 $sumlimits_{x<a_i, y<b_j} z$，记为 $sum$，用 $sum - ca_i - cb_j$ 去更新答案。
时间复杂度 $mathcal O(nmp)$。
Algorithm 2
能不能弄点单调性出来呢？
我们将武器按照 $a$ 排序，怪物按照 $x$ 排序。
这时候，如果我们从小到大枚举武器，而且 只考虑 $x$ 部分的话，能打的怪物也是一个 前缀。
但是只有武器是不行的，还要防具，但要是再枚举不又回到了 Algorithm 1 了吗？这个单调性似乎一点都没用啊？
正难则反，既然没法已知 $b$ 去枚举怪物，我们索性按照 $x$ 属性依次添加怪物，用 $val_b$ 来表示当防具的威力为 $b$ 时，最高的奖励。
如果某一个 $b$ 值的防具都没出现，那么 $val_b$ 自然是 $-infty$，否则，$val_b$ 的 初始值应当是 $-cb_b$，表示一次购买。
那么，对于一个怪物，根据前缀性质，我们可以类似 two-pointers 的加入，怪物的 $x$ 属性自然是满足条件的了，这时将 $[y+1, infty]$ 的 $val_b$ 加上 $z$，表示配合一个威力值至少为 $y+1$ 的防具，就可以肝掉这个怪兽了。
$max{val}$ 就是最优方案，当然 $a$ 的代价是没有考虑进去的，所以用 $max{val}-ca_i$ 更新答案。
实际上，因为 $b le 10^6$，所以修改/查询都进行到 $10^6$ 即可。
时间复杂度 $mathcal O(n ext{ max}{b})$。$p$ 和 $n$ 不区分。
Algorithm 3
进一步分析两个操作。
你干了啥？区间（后缀）加，整体 $max$。
一个线段树直接搞定！
所以用线段树维护 $val$ 数组即可。
时间复杂度 $mathcal{O(n log ext{max}{b})}$。
下面是 AC 代码。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 5;
struct weapon
{
LL a, ca;
bool operator < (const weapon &oth) const { return a < oth.a; }
} wea[N];
struct monster
{
LL x, y, z;
bool operator < (const monster &oth) const { return x < oth.x; }
} mon[N];
LL n, m, p, val[N], ans = LLONG_MIN; // ans 一定要赋极小值！
struct segment_tree // 线段树相关
{
#define ROOT 1, N - 5, 1
#define LSON l, mid, rt << 1
#define RSON mid + 1, r, rt << 1 | 1
struct node
{
LL maxx, col;
} o[N << 2];
inline void update(int rt)
{
o[rt].maxx = max(o[rt << 1].maxx, o[rt << 1 | 1].maxx);
}
void build(int l, int r, int rt)
{
o[rt].col = 0;
if(l == r)
{
o[rt].maxx = val[l];
return;
}
int mid = l + r >> 1;
build(LSON); build(RSON);
update(rt);
}
inline void color(int rt, LL v)
{
o[rt].col += v;
o[rt].maxx += v;
}
inline void pushcol(int rt)
{
if(!o[rt].col) return;
color(rt << 1, o[rt].col);
color(rt << 1 | 1, o[rt].col);
o[rt].col = 0;
}
void modify(int l, int r, int rt, int ml, int mr, LL v)
{
if(ml <= l && r <= mr)
{
color(rt, v);
return;
}
int mid = l + r >> 1;
pushcol(rt);
if(ml <= mid) modify(LSON, ml, mr, v);
if(mr > mid) modify(RSON, ml, mr, v);
update(rt);
}
} sgt;
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m >> p;
for(register int i = 1; i < N; i++) val[i] = LLONG_MIN;
for(register int i = 1; i <= n; i++) cin >> wea[i].a >> wea[i].ca;
for(register int i = 1; i <= m; i++)
{
LL b, cb;
cin >> b >> cb;
val[b] = max(val[b], -cb); // 更新线段树初始叶子节点权值
}
sgt.build(ROOT);
sort(wea + 1, wea + n + 1);
for(register int i = 1; i <= p; i++) cin >> mon[i].x >> mon[i].y >> mon[i].z;
sort(mon + 1, mon + p + 1);
int cur = 1;
for(register int i = 1; i <= n; i++)
{
while(cur <= p && wea[i].a > mon[cur].x) // 类似 two-pointers 计算贡献
{
if(mon[cur].y != N - 5)
sgt.modify(ROOT, mon[cur].y + 1, N - 5, mon[cur].z);
cur++;
}
ans = max(ans, sgt.o[1].maxx - wea[i].ca); // 全局 max，也就是根节点
}
cout << ans << endl;
return 0;
}
Algorithm 4
什么？$10^6$ 带 $log$ 不稳？
离散化解决一切！
时间复杂度 $mathcal O(nlog m)$。本质上就是去掉了 $val = -infty$ 的情况。
当然，这个优化是完全不必要的。