官方题解:
// 离线树状数组 hihocoder 1391 Countries #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <math.h>
#include <memory.h>
using namespace std;
#define LL long long
typedef pair<int,int> pii;
const LL inf = 0x3f3f3f3f;
const LL MOD =100000000LL;
// const int N = 1e5+10;
const double eps = 1e-;
void fre() {freopen("in.txt","r",stdin);}
void freout() {freopen("out.txt","w",stdout);}
inline int read() {int x=,f=;char ch=getchar();while(ch>''||ch<'') {if(ch=='-') f=-; ch=getchar();}while(ch>=''&&ch<='') {x=x*+ch-'';ch=getchar();}return x*f;}
const int MAXN = ;
struct node{
LL l,r,v;
}N[MAXN]; LL f[MAXN],x[MAXN];
int cmp(node a,node b){
return a.r<b.r;
}
void add(LL w,LL v){
for(;w<=MAXN;w+=w&(-w)) f[w]+=v;
}
LL getsum(LL w){
LL sum=;
for(;w;w-=w&(-w)) sum+=f[w];
return sum;
} int main(){
LL n,m,bs,nn,M;
while(~scanf("%lld%lld",&n,&m)){
memset(f,,sizeof(f));
memset(x,,sizeof(x));
scanf("%lld",&bs);
scanf("%lld%lld",&nn,&M);
LL r=m+bs;
LL k=;
LL sum=;
for(LL i=;i<=nn;i++){
LL s,t,v;
scanf("%lld%lld%lld",&s,&t,&v);
if(s+t<bs||s+t>r) continue;
else{
N[++k].l=s+*t,N[k].r=s+*t+(r-s-t)/(*t)**t;
N[k].v=v;
sum+=v;
}
}
for(LL i=;i<=M;i++){
LL s,t,v;
scanf("%lld%lld%lld",&s,&t,&v);
N[++k].l=s+t,N[k].v=v;
sum+=v;
if(s+t*<bs||s+t*>r) N[k].r=N[k].l;
else{
N[k].r=s+*t+(r-s-*t)/(*t)**t;
}
}
LL g=k;
k=;
for(LL i=;i<=g;i++){
x[++k]=N[i].l,x[++k]=N[i].r,x[++k]=N[i].r-n;
}
sort(N+,N++g,cmp);
sort(x+,x++k);
k=unique(x+,x++k)-x-;
LL ans=-inf;
for(LL i=;i<=g;i++){
LL w,pre,now;
w=lower_bound(x+,x++k,N[i].l)-x;
now=lower_bound(x+,x++k,N[i].r)-x;
pre=lower_bound(x+,x++k,N[i].r-n)-x;
add(w,N[i].v);
ans=max(ans,getsum(now)-getsum(pre-));
}
printf("%lld\n",sum-ans);
}
return ;
}