链接
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 */