关于线段树求解该题目(参考大佬解法)
(线段树扫描)
假设炸弹辐射半径为r
首先根据x轴建立关于坐标y的线段树,然后线性扫描,每经过一个城市坐标(xi,yi,wi),xi所对应的(yi+1,yi+r)区域的炸弹均可以辐射该城市,所以权重加wi,而炸弹经过xi+r之后的区域,该城市已经无法覆盖,故而权重为-wi,这里大佬的代码里没有进行权重的排序,但不进行排序答案会偏大,因为我们在扫描过程中,首先要处理负权重,否则会将无效城市计算进来。
代码中有详细注释,实在不懂可以画一下图,每次固定x轴,然后向上扫描一遍(也就是本题目中的扔炸弹),然后x向右移继续沿y轴扫描,每次更新线段树,并更新答案。
时间复杂度 $O(NlgM)$,N为城市数,M为坐标范围
参考题解:米4达girl
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int maxn=1e5+233;
int x,y,z,n,radius;
struct Node{
int l,r,w,m;
}t[maxn*4];
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(l==r){t[p].w=0,t[p].m=0;return;}
int mid = (l+r)>>1;
build(p<<1,l,mid);
build((p<<1)+1,mid+1,r);
t[p].w=0,t[p].m=0;
}
void spr(int p){
if(t[p].m){
t[p<<1].m+=t[p].m;
t[(p<<1)+1].m+=t[p].m;
t[p<<1].w+=t[p].m;
t[(p<<1)+1].w+=t[p].m;
t[p].m=0;
}
}
void update(int p,int l,int r,int w){
if(t[p].l>=l&&t[p].r<=r){
t[p].w+=w;t[p].m+=w;
return;
}
spr(p);
int mid=(t[p].l+t[p].r)>>1;
if(mid>=l) update(p<<1,l,r,w);
if(mid<r) update((p<<1)+1,l,r,w);
t[p].w=max(t[p<<1].w,t[(p<<1)+1].w);
}
int ask(int p,int l,int r){
if(t[p].l>=l&&t[p].r<=r)return t[p].w;
spr(p);
int mid=(t[p].l+t[p].r)>>1;
int res=0;
if(mid>=l) res=max(res,ask(p<<1,l,r));
if(mid<r) res=max(res,ask((p<<1)+1,l,r));
return res;
}
const bool comp(const pair<int,pair<int,pii>> &a,const pair<int,pair<int,pii>> &b){
if(a.first<b.first)
return true;
else if(a.first==b.first)
return a.second.first<=b.second.first;
return false;
}
int main(){
cin>>n>>radius;
vector<pair<int,pair<int,pii>>> org;//记录坐标与权重
for(int i=0;i<n;i++){
cin>>x>>y>>z;
y++;
org.push_back({x,{z,{y,y+radius-1}}});
org.push_back({x+radius,{-z,{y,y+radius-1}}});
}
sort(org.begin(),org.end(),comp);//排序,按x轴线性扫描,并且权重从小到大
build(1,1,20001);//建树
int ans=0;
for(int i=0;i<org.size();i++){
pii now=org[i].second.second;
int ty = org[i].second.first;
// cout<<org[i].first<<endl;
//每次更新线段树区域(now.first,now.second),大佬未进行排序,我提交上去是错误的,原因可能是必须首先处理负权重,否则答案错误,偏大
update(1,now.first,now.second,ty);
//查询当前最大值
ans=max(ans,ask(1,1,20001));
}
cout<<ans<<endl;
return 0;
}