题意：平面上n个点，每个点带有一个或正或负的权值，让你在平面上放一个内边长为2l，外边长为2r的正方形框，问你最大能圈出来的权值和是几多？
容易推出，能框到每个点的 框中心 的范畴也是一个以该点为中心的不异巨细的框。
于是，把每个点的框拆成4条线。从下往上扫过去，最下面的线，给[R,R]区间加上该点的权值，然后上面再给[L,L]减去，然后上面再给[L,L]加上，然后再往上在给[R,R]减去即可。每次扫完一行，就用线段树的全局最大值测验考试更新答案。
两个坑点：首先，由于线段树里存储的是离散后的点，所以有可能会存在一些死角，所以给离散化后的每两个点之间再插入一个点，这样不会有死角。
其次，出边对应的线要向上移动一个单位，并且摆布端点向内缩小一个单位，这样便利措置惩罚惩罚。
（UPDATE：虽然AC了此题，，但是被HACK了，怀疑是“出边对应的线要向上移动一个单位，并且摆布端点向内缩小一个单位”这里有BUG）
#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; struct data{ int p; ll v; }t[1200005]; int a[1200005]; bool cmp(const data &a,const data &b){ return a.v<b.v; } struct LINE{ int y; int l,r; int w; bool in; }lines[400005]; bool cm2(const LINE &a,const LINE &b){ return a.y!=b.y ? a.y<b.y : a.in>b.in; } int n,L,R,e,zy; int y[100005],z[100005],ans; int maxv[4800005],delta[4800005]; void pushdown(int rt){ if(delta[rt]){ delta[rt<<1]+=delta[rt]; delta[rt<<1|1]+=delta[rt]; maxv[rt<<1]+=delta[rt]; maxv[rt<<1|1]+=delta[rt]; delta[rt]=0; } } void update(int ql,int qr,int v,int rt,int l,int r){ if(ql<=l && r<=qr){ maxv[rt]+=v; delta[rt]+=v; return; } int m=(l+r>>1); pushdown(rt); if(ql<=m){ update(ql,qr,v,rt<<1,l,m); } if(m<qr){ update(ql,qr,v,rt<<1|1,m+1,r); } maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]); } int main(){ // freopen("a.in","r",stdin); int x; scanf("%d%d%d",&n,&L,&R); for(int i=1;i<=n;++i){ scanf("%d%d%d",&x,&y[i],&z[i]); t[++e].v=(ll)(x-R)*2ll; t[e].p=e; t[++e].v=(ll)(x-R)*2ll-1ll; t[e].p=e; t[++e].v=(ll)(x-R)*2ll+1ll; t[e].p=e; t[++e].v=(ll)(x-L+1)*2ll; t[e].p=e; t[++e].v=(ll)(x-L+1)*2ll-1ll; t[e].p=e; t[++e].v=(ll)(x-L+1)*2ll+1ll; t[e].p=e; t[++e].v=(ll)(x+L-1)*2ll; t[e].p=e; t[++e].v=(ll)(x+L-1)*2ll-1ll; t[e].p=e; t[++e].v=(ll)(x+L-1)*2ll+1ll; t[e].p=e; t[++e].v=(ll)(x+R)*2; t[e].p=e; t[++e].v=(ll)(x+R)*2-1; t[e].p=e; t[++e].v=(ll)(x+R)*2+1; t[e].p=e; } sort(t+1,t+e+1,cmp); a[t[1].p]=++zy; for(int i=2;i<=e;++i){ if(t[i].v!=t[i-1].v){ ++zy; } a[t[i].p]=zy; } for(int i=1;i<=n;++i){ lines[i*4-3].y=y[i]-R; lines[i*4-2].y=y[i]-L+1; lines[i*4-1].y=y[i]+L; lines[i*4-0].y=y[i]+R+1; lines[i*4-3].l=a[i*12-11]; lines[i*4-2].l=a[i*12-8]; lines[i*4-1].l=a[i*12-8]; lines[i*4-0].l=a[i*12-11]; lines[i*4-3].r=a[i*12-2]; lines[i*4-2].r=a[i*12-5]; lines[i*4-1].r=a[i*12-5]; lines[i*4-0].r=a[i*12-2]; lines[i*4-3].w=z[i]; lines[i*4-2].w=z[i]; lines[i*4-1].w=z[i]; lines[i*4-0].w=z[i]; lines[i*4-3].in=1; lines[i*4-2].in=0; lines[i*4-1].in=1; lines[i*4-0].in=0; } sort(lines+1,lines+(n<<2|1),cm2); for(int i=1;i<=(n<<2);++i){ if(lines[i].in){ update(lines[i].l,lines[i].r,lines[i].w,1,1,zy); } else{ update(lines[i].l,lines[i].r,-lines[i].w,1,1,zy); } if(lines[i].y!=lines[i+1].y){ ans=max(ans,maxv[1]); } } printf("%d\n",ans); return 0; }
【线段树】【扫描线】Petrozavodsk Winter Training Camp 2018 Day 5: Grand Prix of Korea, Sunday, February 4, 2018 Problem A. Donut
标签：
原文地点：https://www.cnblogs.com/autsky-jadek/p/8975493.html