注意到攻击力和防御力上限为1e6，对防御力建一颗线段树，初始存防御力至少为i的盔甲的金额的负数。扫描攻击力，每次把当前攻击力能打动的怪的金钱加到比怪防御力高的结点上，更新答案。
1 #define HAVE_STRUCT_TIMESPEC 2 #include<bits/stdc++.h> 3 using namespace std; 4 long long a[200007],b[200007],c[2000007],d[200007],e[200007],f[200007],g[200007]; 5 long long x[1000007],y[1000007]; 6 long long mx[4000007],lz[4000007],mxid[4000007]; 7 void up(long long rt){ 8 if(mx[rt<<1]>=mx[rt<<1|1]){ 9 mx[rt]=mx[rt<<1]; 10 mxid[rt]=mxid[rt<<1]; 11 } 12 else{ 13 mx[rt]=mx[rt<<1|1]; 14 mxid[rt]=mxid[rt<<1|1]; 15 } 16 } 17 void down(long long rt){ 18 lz[rt<<1]+=lz[rt]; 19 lz[rt<<1|1]+=lz[rt]; 20 mx[rt<<1]+=lz[rt]; 21 mx[rt<<1|1]+=lz[rt]; 22 lz[rt]=0; 23 } 24 void build(long long rt,long long l,long long r){ 25 if(l==r){ 26 mx[rt]=-y[l]; 27 mxid[rt]=l; 28 return ; 29 } 30 build(rt<<1,l,(l+r)>>1); 31 build(rt<<1|1,((l+r)>>1)+1,r); 32 up(rt); 33 } 34 void update(long long rt,long long l,long long r,long long L,long long R,long long k){ 35 if(L>R) 36 return ; 37 if(L<=l&&r<=R){ 38 lz[rt]+=k; 39 mx[rt]+=k; 40 return ; 41 } 42 down(rt); 43 if(L<=((l+r)>>1)) 44 update(rt<<1,l,(l+r)>>1,L,R,k); 45 if(R>((l+r)>>1)) 46 update(rt<<1|1,((l+r)>>1)+1,r,L,R,k); 47 up(rt); 48 } 49 long long cmx,cid; 50 void query(long long rt,long long l,long long r,long long L,long long R){ 51 if(L<=l&&r<=R){ 52 if(mx[rt]>cmx){ 53 cmx=mx[rt]; 54 cid=mxid[rt]; 55 } 56 return ; 57 } 58 down(rt); 59 if(L<=((l+r)>>1)) 60 query(rt<<1,l,(l+r)>>1,L,R); 61 if(R>((l+r)>>1)) 62 query(rt<<1|1,((l+r)>>1)+1,r,L,R); 63 } 64 vector<pair<long long,long long> >v[1000007]; 65 int main(){ 66 ios::sync_with_stdio(false); 67 cin.tie(NULL); 68 cout.tie(NULL); 69 long long n; 70 cin>>n; 71 long long m; 72 cin>>m; 73 long long p; 74 cin>>p; 75 for(long long i=1;i<=n;++i){ 76 cin>>a[i]>>b[i]; 77 if(!x[a[i]]) 78 x[a[i]]=b[i]; 79 else 80 x[a[i]]=min(x[a[i]],b[i]);//武器攻击力至少为a[i]保留最低的价格 81 } 82 for(long long i=1;i<=m;++i){ 83 cin>>c[i]>>d[i]; 84 if(!y[c[i]]) 85 y[c[i]]=d[i]; 86 else 87 y[c[i]]=min(y[c[i]],d[i]);//盔甲防御力至少为c[i]保留最低的价格 88 } 89 for(long long i=1;i<=p;++i){ 90 cin>>e[i]>>f[i]>>g[i]; 91 v[e[i]+1].push_back({f[i]+1,g[i]});//至少武器攻击力为e[i]+1才能打动的怪，防御力至少为f[i]+1才能挡住的怪 92 } 93 long long r=0; 94 for(long long i=1000000;i;--i){ 95 if(!r&&y[i]) 96 r=i; 97 if(x[i+1]){ 98 if(x[i]==0) 99 x[i]=x[i+1]; 100 else 101 x[i]=min(x[i],x[i+1]); 102 } 103 if(y[i+1]){ 104 if(y[i]==0) 105 y[i]=y[i+1]; 106 else 107 y[i]=min(y[i],y[i+1]); 108 } 109 } 110 build(1,1,r);//把盔甲的金钱取负先计算到结点中 111 long long ans=-2e18; 112 for(long long i=1;i<=1000000;++i){//枚举武器攻击力，攻击力小的武器能打动的怪，攻击力大的武器一定能打的动，所以贡献可以推移 113 if(x[i]==0)//没有这么强力的武器了 114 break; 115 for(auto it:v[i])//遍历防御力为i-1的怪物 116 update(1,1,r,it.first,r,it.second);//盔甲防御力在it.first及以上的都可以用当前武器配合起来吃掉这只怪，把打怪的钱加到结点上 117 ans=max(ans,mx[1]-x[i]);//更新答案，怪的钱数总和去掉武器和盔甲的花费 118 } 119 cout<<ans; 120 return 0; 121 }