题目链接：http://codeforces.com/contest/1321/problem/E
题目大意：
给定一系列有代价的装备，第一种提供 x 值，第二种提供 y 值。给出一些怪兽，如果怪兽的 xi 和 yi 都小于选定的 x 和 y ，那么会有 zi 的奖励。最大化收益。
思路：
我们可以先把它转化成一个二维坐标系，对于不同的 x 和不同的 y 都有一个特定的代价，而对于每个点来说它又会有一个贡献值。
首先我们可以知道对于每一个特定的 x ，都有一个最优的 y 可以与之对应。那么我们可以考虑采取线段树去维护 y 的区间最优解。
至于每一个有贡献的点添进来的时候，其实就只需要在当前 [y+1,maxn] 这个区间上加上这个点的贡献就可以了。
#include <algorithm> #include <string> #include <string.h> #include <vector> #include <map> #include <stack> #include <set> #include <queue> #include <math.h> #include <cstdio> #include <iomanip> #include <time.h> #include <bitset> #include <cmath> #include <sstream> #include <iostream> #define LL long long #define ls nod<<1 #define rs (nod<<1)+1 #define pii pair<int,int> #define mp make_pair const double eps = 1e-10; const int maxn = 1e6 + 1; const LL mod = 1e9 + 7; const LL INF = 1e18; int sgn(double a){return a < -eps ? -1 : a < eps ? 0 : 1;} using namespace std; struct segment_tree { LL val; int lazy; }tree[maxn << 2]; LL a[maxn],b[maxn]; vector<pii> vec[maxn]; void build (int l,int r,int nod) { if (l == r) { tree[nod].val = -b[l]; return ; } int mid = (l + r ) >> 1; build(l,mid,ls); build(mid+1,r,rs); tree[nod].val = max(tree[ls].val,tree[rs].val); } void pushdown(int nod) { tree[ls].lazy += tree[nod].lazy; tree[rs].lazy += tree[nod].lazy; tree[ls].val += tree[nod].lazy; tree[rs].val += tree[nod].lazy; tree[nod].lazy = 0; } void modify(int l,int r,int ql,int qr,int k,int nod) { if (ql <= l && qr >= r) { tree[nod].lazy += k; tree[nod].val += k; return ; } if (tree[nod].lazy) pushdown(nod); int mid = (l + r) >> 1; if (ql <= mid) modify(l,mid,ql,qr,k,ls); if (qr > mid) modify(mid+1,r,ql,qr,k,rs); tree[nod].val = max(tree[ls].val,tree[rs].val); } LL query(int l,int r,int ql,int qr,int nod) { if (ql <= l && qr >= r) return tree[nod].val; if (tree[nod].lazy) pushdown(nod); int mid = (l + r ) >> 1; LL ans = 0; if (ql <= mid) ans += query(l,mid,ql,qr,ls); if (qr > mid) ans += query(mid+1,r,ql,qr,rs); return ans; } int main() { ios::sync_with_stdio(false); for (int i = 0;i <= maxn;i++) a[i] = b[i] = INF; int n,m,p; cin >> n >> m >> p; for (int i = 1;i <= n;i++) { int x; LL y; cin >> x >> y; a[x] = min(a[x],y); } for (int i = 1;i <= m;i++) { int x; LL y; cin >> x >> y; b[x] = min(b[x],y); } for (int i = 1;i <= p;i++) { int x,y,z; cin >> x >> y >> z; vec[x].push_back(mp(y,z)); } build(1,maxn,1); LL ans = -INF; for (int i = 1;i <= maxn;i++) { ans = max(ans,tree[1].val-a[i]); for (pii o : vec[i]) { if (o.first+1 < maxn) modify(1,maxn,o.first+1,maxn,o.second,1); } } cout << ans << endl; return 0; }