59 懒惰的奶牛
贝西所在的牧场，散落着 N 堆牧草，其中第 i 堆牧草在 ( Xi,Yi ) 的位置，数量有 Ai 个单位。
贝西从家移动到某一堆牧草的时候，只能沿坐标轴朝正北、正东、正西、正南这四个方向移
动，所以计算贝西和牧草间的距离时，应采用“曼哈顿距离”—— (x,y ) 和 (x ′,y ′) 之间的距离为
|x − x ′ | + |y − y ′ |。例如贝西的家在 (0.5, 0.3)，有一堆牧草在 (3, 2)，那么它们之间的距离就是 4.2。
贝西懒得走动，她想请你为它寻找一个最好的位置作为家，这个家附近距离不超过 K 的牧草数
量之和是最大的。注意家的坐标可以不是整数，也可以和某堆牧草的坐标完全重合。
输入格式
• 第一行：两个整数 N 和 K， 1 ≤ N ≤ 100000, 1 ≤ K ≤ 2000000
• 第二行到第 N + 1 行：第 i + 1 行有三个整数： Ai, Xi 和 Yi， 1 ≤ Ai ≤ 10000, 0 ≤ Xi,Yi ≤
1000000
输出格式
• 单个整数：表示距离和最佳位置不超过 K 的牧草数量之和
样例输入
4 3
7 8 6
3 0 0
4 6 0
1 4 2
样例输出
8
解释
选择 (3, 0) 为家，位置在 (0, 0)， (6, 0) 和
(4, 2) 的牧草距离家都不超过 K
来源
The Lazy Cow, 2014 Mar
【分析】
曼哈顿距离的话，那个范围，应该是一个边长和坐标轴呈45度角的正方形。
这样就有点难搞，难统计。
我们需要把图形“旋转一下”
旋转的目标是让正方形的边长平行于坐标轴。、
那么，观察一下可以得到，可以把nx=x-y ny=x+y 这样就旋转过来了（其实改变了正方形的大小的，但没有关系，只要能判断出曼哈顿距离是不是<=k就好）
然后就很简单了，用线段树维护y纵坐标，然后x横坐标线性扫描。
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
#define Maxn 2000010 struct hp
{
int a,ax,ay;
}tt[Maxn]; struct node
{
int l,r,lc,rc,ans;
int lazy;
}t[*Maxn];int len; int mymin(int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;} bool cmp(hp x,hp y) {return x.ax<y.ax;}
int n,k; int build(int l,int r)
{
int x=++len;
t[x].l=l;t[x].r=r;
t[x].ans=;t[x].lazy=;
if(l!=r)
{
int mid=(l+r)>>;
t[x].lc=build(l,mid);
t[x].rc=build(mid+,r);
}
else t[x].lc=t[x].rc=;
return x;
} void init()
{
scanf("%d%d",&n,&k);
int mx=;
for(int i=;i<=n;i++)
{
scanf("%d%d%d",&tt[i].a,&tt[i].ax,&tt[i].ay);
int xx=tt[i].ax;
tt[i].ax=tt[i].ax-tt[i].ay;tt[i].ay=xx+tt[i].ay+;
mx=mymax(mx,tt[i].ay);
}
sort(tt+,tt++n,cmp);
k=k*;
build(,mx);
} void upd(int x)
{
if(t[x].lazy==) return;
t[x].ans+=t[x].lazy;
int lc=t[x].lc,rc=t[x].rc;
if(t[x].l!=t[x].r)
{
t[lc].lazy+=t[x].lazy;
t[rc].lazy+=t[x].lazy;
}
t[x].lazy=;
} void change(int x,int l,int r,int y)
{
if(t[x].l==l&&t[x].r==r)
{
t[x].lazy+=y;
return;
}
upd(x);
int mid=(t[x].l+t[x].r)>>;
if(r<=mid) change(t[x].lc,l,r,y);
else if(l>mid) change(t[x].rc,l,r,y);
else
{
change(t[x].lc,l,mid,y);
change(t[x].rc,mid+,r,y);
}
upd(t[x].lc);upd(t[x].rc);
t[x].ans=mymax(t[t[x].lc].ans,t[t[x].rc].ans);
} void ffind()
{
int j=,ans=;
for(int i=;i<=n;i++)
{
while(j<n&&tt[j+].ax-tt[i].ax<=k)
{
int nx=mymax(,tt[j+].ay-k);
change(,nx,tt[j+].ay,tt[j+].a);
j++;
}
upd();
ans=mymax(ans,t[].ans);
change(,mymax(,tt[i].ay-k),tt[i].ay,-tt[i].a);
}
printf("%d\n",ans);
} int main()
{
init();
ffind();
return ;
}
bzoj 3476
2016-10-31 11:25:57