BZOJ3476 : [Usaco2014 Mar]The Lazy Cow

旋转坐标系后转化为正方形，$x'=x+y$，$y'=x-y+1000001$，$k'=2k-1$

两根扫描线从左往右扫

f[i]表示y坐标下边界为i时的价值和

每次加入/删除一个点等价于一段区间加减

然后查询全局最大值

线段树维护扫描线之间的点

 

 

#include<cstdio> #include<algorithm> const int E=1000001,N=E*2-1,M=N*4+10; struct P{int x,y,g;}a[100010]; inline bool cmp(P a,P b){return a.x<b.x;} int n,m,k,i,j,x,y,ans,v[M],tag[M]; inline void add1(int x,int p){v[x]+=p,tag[x]+=p;} void add(int x,int a,int b,int c,int d,int p){if(c<=a&&b<=d){add1(x,p);return;}if(tag[x])add1(x<<1,tag[x]),add1(x<<1|1,tag[x]),tag[x]=0;int mid=(a+b)>>1;if(c<=mid)add(x<<1,a,mid,c,d,p);if(d>mid)add(x<<1|1,mid+1,b,c,d,p);v[x]=v[x<<1]>v[x<<1|1]?v[x<<1]:v[x<<1|1]; } int main(){scanf("%d%d",&n,&k);k=k*2+1;for(i=1;i<=n;i++)scanf("%d%d%d",&a[i].g,&x,&y),a[i].x=x+y,a[i].y=x-y+E;std::sort(a+1,a+n+1,cmp);for(i=j=1;i<=n;i++){while(a[i].x-a[j].x+1>k)add(1,1,N,a[j].y-k+1,a[j].y,-a[j].g),j++;add(1,1,N,a[i].y-k+1,a[i].y,a[i].g);if(ans<v[1])ans=v[1];}return printf("%d",ans),0; }

　　

总结

以上是生活随笔为你收集整理的BZOJ3476 : [Usaco2014 Mar]The Lazy Cow的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。