cf1321E

攻击武器和怪兽是单调的，只用关心防御武器够打的怪兽，是一个前缀和。

我用线段树上的叶子值表示前缀和，这样每次插入一个怪兽，做区间修改就行了。

/*
* @Author: chenkexing
* @Date:   2020-03-06 11:53:04
* @Last Modified by:   chenkexing
* @Last Modified time: 2020-03-06 14:12:58
*/
#include <algorithm>
#include  <iterator>
#include  <iostream>
#include   <cstring>
#include   <cstdlib>
#include   <iomanip>
#include    <bitset>
#include    <cctype>
#include    <cstdio>
#include    <string>
#include    <vector>
#include     <stack>
#include     <cmath>
#include     <queue>
#include      <list>
#include       <map>
#include       <set>
#include   <cassert>
//#include <unordered_set>
//#include <unordered_map>
// #include<bits/extc++.h>
// using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define fi first
#define se second
#define debug(x) cerr<<#x << " := " << x << endl;
#define bug cerr<<"-----------------------"<<endl;
#define FOR(a, b, c) for(int a = b; a <= c; ++ a)
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
 
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
 
/**********showtime************/
            const int maxn = 2e5+9;
            const int maxm = 1e6+9;
            pii a[maxn],b[maxn];
            bool cmp1(pii a, pii b) {
                if(a.fi == b.fi) {
                    return a.se > b.se;
                }
                return a.fi < b.fi;
            }
            struct Mon{
                int x,y;
                int val;
            }mon[maxn];
            
            bool cmp2(Mon a, Mon b){
                return a.x < b.x;
            }

            ll tree[maxm];
            ll mx[maxm << 2], lazy[maxm << 2];
            void build(int le, int ri, int rt) {
                lazy[rt] = 0;

                if(le == ri) {
                    mx[rt] = -tree[le];
                    return;
                }
                int mid = (le + ri) >> 1;
                build(le, mid, rt<<1);
                build(mid+1, ri, rt<<1|1);
                mx[rt] = max(mx[rt<<1], mx[rt<<1|1]);
            }
            void pushdown(int rt) {
                lazy[rt<<1] += lazy[rt];
                lazy[rt<<1|1] += lazy[rt]; 
                mx[rt<<1] += lazy[rt];
                mx[rt<<1|1] += lazy[rt];
                lazy[rt] = 0;
            }
            void update(int L, int R, int val, int le, int ri, int rt) {
                if(le >= L && ri <= R) {
                    lazy[rt] += val;
                    mx[rt] += val;
                    return;
                }
                if(lazy[rt]) pushdown(rt);
                int mid = (le + ri) >> 1;
                if(mid >= L) update(L, R, val, le, mid, rt<<1);
                if(mid < R)  update(L, R, val, mid+1, ri, rt<<1|1);
                mx[rt] = max(mx[rt<<1], mx[rt<<1|1]);
            }

            
int main(){
            memset(tree, inff, sizeof(tree));
            int n,m,k;  
            scanf("%d%d%d", &n, &m, &k);
            for(int i=1; i<=n; i++) {
                scanf("%d%d", &a[i].fi, &a[i].se);
            }

            for(int i=1; i<=m; i++) {
                scanf("%d%d", &b[i].fi, &b[i].se);
                tree[b[i].fi] =min(tree[b[i].fi], 1ll*b[i].se);
            }

            for(int i=1; i<=k; i++) {
                scanf("%d%d%d", &mon[i].x, &mon[i].y, &mon[i].val);
            }
            int N = 1e6;
            build(1,  N,  1);

            sort(a+1, a+1+n, cmp1);

            sort(mon+1, mon+1+k, cmp2);

            ll ans = -inff;
            int j = 1;
            for(int i=1; i<=n; i++) {
                while(j <= k && mon[j].x < a[i].fi) {
                    if(mon[j].y + 1 <= N) 
                        update(mon[j].y + 1, N, mon[j].val, 1, N, 1);
                    j++;
                }
                ans = max(ans, mx[1] - a[i].se);
                // cout<<i << " :: " << mx[1]<<endl;
            }

            printf("%lld
", ans);
            return 0;
}