Codeforces Round #625 World of Darkraft: Battle for Azathoth

链接
Answer ：
可以把怪兽看成二维坐标上的一些点，每个点有一些权值。
然后对于所有的x=ai（攻击）的轴上都有m个bi（防御）那么对于每一个bi它所能打死的所有怪兽就是当前的轴的左面所有y小于bi的怪兽
所以问题就转化为一个区间求和+区间最大值的问题 用线段树维护就好了

坑点:把握好题目给的条件，以及输入顺序（怪兽是先给的防御力 …好坑）
Code：

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;

const int maxn = 2e6+5;
const LL inf = 0x3f3f3f3f3f3f3f3f;

int n,m,p,vis[maxn];
pair<int,int>a[maxn],b[maxn];
pair<pair<int,int>,int>c[maxn];
LL lazy[maxn],ma[maxn];
int ub(int x){
    int l=1,r=m,ans=m+1;
    while(l<=r){
        int mid=l+r>>1;
        if(b[mid].fi<=x){
            l=mid+1;
        } else {
            ans=min(ans,mid);
            r=mid-1;
        }
    }
    return ans;
}
void push_up(int rt,int l,int r){
     ma[rt]=max(ma[rt<<1],ma[rt<<1|1]);
}
void push_down(int rt,int l,int r){
     if(lazy[rt]){
        lazy[rt<<1]+=lazy[rt];
        ma[rt<<1]+=lazy[rt];

        lazy[rt<<1|1]+=lazy[rt];
        ma[rt<<1|1]+=lazy[rt];
        lazy[rt]=0;
     }
}

void update(int rt,int l,int r,int x,int y,LL val){
      if(x<=l&&r<=y){
         lazy[rt]+=val;ma[rt]+=val;
         return ;
      }
      push_down(rt,l,r);
      int mid=l+r>>1;
      if(x<=mid) update(rt<<1,l,mid,x,y,val);
      if(y>mid) update(rt<<1|1,mid+1,r,x,y,val);
      push_up(rt,l,r);
}
int main(){
    scanf("%d%d%d",&n,&m,&p);
    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);
    }
    for(int i=1;i<=p;i++){
        scanf("%d%d%d",&c[i].fi.fi,&c[i].fi.se,&c[i].se);
    }

    sort(a+1,a+1+n);
    sort(b+1,b+1+m);
    sort(c+1,c+1+p);
   // init();
    //cout<<n<<','<<m<<'\n';
    for(int i=1;i<=m;i++){
        update(1,1,m,i,i,-b[i].se);
    }
    //cout<<ma[1]<<endl;
    LL ans=-inf,res=0,t=1;
    for(int i=1;i<=n;i++){
        while(t<=p&&c[t].fi.fi<a[i].fi){
            int pos=ub(c[t].fi.se);
            //cout<<i<<','<<pos<<','<<c[t].fi.se<<endl;
            if(pos<=m)
            update(1,1,m,pos,m,c[t].se);
            t++;
        }
        res=ma[1]-a[i].se;
        ans=max(ans,res);
        //printf("%lld %lld\n",ma[1],ans);
    }
    printf("%lld\n",ans);
}
/* 3 3 3 6 1010 9 1153 9 1159 9 1150 7 1058 9 1159 7 3 172 10 3 167 6 6 160 */