应该也可以用线段树/树状数组区间更新怪兽的生命值来做
1 #define HAVE_STRUCT_TIMESPEC 2 #include<bits/stdc++.h> 3 using namespace std; 4 long long pre[200007]; 5 int main(){ 6 ios::sync_with_stdio(false); 7 cin.tie(NULL); 8 cout.tie(NULL); 9 long long n,d,a; 10 cin>>n>>d>>a; 11 vector<pair<long long,long long> >v; 12 for(int i=1;i<=n;++i){ 13 long long x,y; 14 cin>>x>>y; 15 long long z=(y-1)/a+1; 16 v.push_back({x,z}); 17 } 18 sort(v.begin(),v.end()); 19 long long ans=0; 20 long long sum=0; 21 int r=1;//打不到的最近范围 22 for(int i=0;i<n;++i){ 23 while(r<n&&v[r].first<=v[i].first+2*d) 24 ++r; 25 sum-=pre[i];//sum为当前位置已经预先承受的伤害总量 26 v[i].second-=sum; 27 if(v[i].second<=0) 28 continue; 29 sum+=v[i].second;//累计伤害 30 pre[r]+=v[i].second;//r位置以前承受的伤害总量 31 ans+=v[i].second; 32 } 33 cout<<ans; 34 return 0; 35 }