CodeForces-1321E Battle for Azathoth

传送门：CodeForces-1321E

思路分析

将武器和防具从小到大排序，怪物按防御力从小到大排序
因为武器是递增的，所以能杀死的怪物是逐渐增多的，怎么计算贡献呢
对于每一件防具，加上能抵抗的怪物的价值，那么在枚举武器的时候，同时枚举怪物，对于每一只怪物，更新所有防具的贡献
防具区间可以通过二分查找实现，然后更新操作可以通过线段树区间覆盖完成，维护一下区间最大值

样例输入

2 3 3
2 3
4 7
2 4
3 2
5 11
1 2 4
2 1 6
3 4 6

样例输出

1

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 1e18;
const int N=1e6+10;

struct node {
    int l,r,mid,ma,lazy;
} tree[N<<2];

struct wuqi {
    int a,b;
    bool operator <(const wuqi &x)const {
        return a<x.a;
    }
} a[N];

struct fangju {
    int a,b;
    bool operator <(const fangju &x)const {
        return a<x.a;
    }
} b[N];

struct guaiwu {
    int a,b,c;
    bool operator <(const guaiwu &x)const {
        return a<x.a;
    }
} c[N];

int d[N];

void pp(int x) {
    tree[x].ma=max(tree[ls].ma,tree[rs].ma);
}

void pd(int x) {
    if(tree[x].lazy) {
        tree[ls].lazy+=tree[x].lazy;
        tree[rs].lazy+=tree[x].lazy;
        tree[ls].ma+=tree[x].lazy;
        tree[rs].ma+=tree[x].lazy;
        tree[x].lazy=0;
    }
}

void build(int x,int l,int r) {
    tree[x]= {l,r,l+r>>1,0,0};
    if(l==r) {
        tree[x].ma=-b[l].b;
        return ;
    }
    int mid=tree[x].mid;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pp(x);
}

void change(int x,int l,int r,int k) {
    if(l<=tree[x].l&&tree[x].r<=r) {
        tree[x].lazy+=k;
        tree[x].ma+=k;
        return;
    }
    pd(x);
    int mid=tree[x].mid;
    if(l<=mid)
        change(ls,l,r,k);
    if(r>mid)
        change(rs,l,r,k);
    pp(x);
}

signed main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int n,m,p;
    cin>>n>>m>>p;
    for(int i=1; i<=n; i++) cin>>a[i].a>>a[i].b;
    for(int i=1; i<=m; i++) cin>>b[i].a>>b[i].b;
    for(int i=1; i<=p; i++) cin>>c[i].a>>c[i].b>>c[i].c;

    sort(a+1,a+1+n);
    sort(b+1,b+1+m);
    sort(c+1,c+1+p);
    for(int i=1; i<=m; i++) d[i]=b[i].a;

    build(1,1,m);
    
    int ans=-INF;
    for(int i=1,pos=1; i<=n; i++) {
        while(pos<=p && c[pos].a<a[i].a) {
            int w=upper_bound(d+1,d+1+m,c[pos].b)-d;
            if(w<=m)
                change(1,w,m,c[pos].c);
            pos++;
        }
        ans=max(ans,tree[1].ma-a[i].b);
    }
    cout<<ans<<endl;



    return 0;
}