Tang Problem
题意
有 \(n\) 个草地的坐标（相当于点），我们需要选择一个点，使得与他距离小于等于 \(k\) 的草地最多。
这里定义的距离就是从起点开始，可以往东西南北走，一次走一个单位长度，最短到达目的地的行走次数。
做法
这个做法需要会切比雪夫距离和曼哈顿距离的互化，并且熟练掌握了扫描线。
这个也是好做的，我们很好想到这个使用扫描线是可以做的，暴力扫 x 轴，数据结构维护 y 轴，合法区域就像一个菱形一样，理论上 \(O(nlogn)\) 是可以做的。
但问题就是这个菱形并不是正的，而是歪的，让我们维护起来就十分的头大。
为什么这个是歪的？自然是因为这个距离的计算方式其实就是曼哈顿距离。
我们把这个转化称切比雪夫距离不就相当于将这个摆正了吗？
所以我们转化一下，\((x,y)\to(x+y,x-y)\)。
之后我们就很容易使用扫描线求解了。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
namespace DataStructure{const int MN=1e6+116;struct Segmentree{#define lc k<<1#define rc k<<1|1struct Node{int l, r, maxn, tag;}tr[MN];void pushup(int k){tr[k].maxn=max(tr[lc].maxn,tr[rc].maxn);}void build(int k, int l, int r){tr[k].l=l, tr[k].r=r; tr[k].tag=0;if(l==r){tr[k].maxn=0; return;}int mid=(l+r)>>1;build(lc,l,mid);build(rc,mid+1,r);pushup(k); return;}void pushdown(int k){if(tr[k].tag==0) return;tr[lc].maxn+=tr[k].tag;tr[rc].maxn+=tr[k].tag;tr[lc].tag+=tr[k].tag;tr[rc].tag+=tr[k].tag;tr[k].tag=0;}void update(int k, int l, int r, int val){if(tr[k].l>=l&&tr[k].r<=r){tr[k].maxn+=val; tr[k].tag+=val; return;}pushdown(k); int mid=(tr[k].l+tr[k].r)>>1;if(l<=mid) update(lc,l,r,val);if(r>mid) update(rc,l,r,val);pushup(k); return;}};
}
int n, k;
const int MN=1e6+116;
DataStructure::Segmentree tr;
struct Node{int x, y1, y2, id;bool operator < (const Node &o) const{if(x!=o.x) return x<o.x;return id>o.id;}
}point[MN],query[MN];
int lsh[MN], ans=0;
int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin>>n>>k;for(int i=1,val,xa,ya; i<=n; ++i){cin>>val>>xa>>ya;xa+=ya; ya=xa-ya*2;int xb=xa+2*k, yb=ya+2*k;point[i*2-1]={xa,ya,yb,val};point[i*2]={xb,ya,yb,-val};lsh[i*2-1]=ya; lsh[i*2]=yb;}sort(point+1,point+n*2+1);sort(lsh+1,lsh+n*2+1);int len=unique(lsh+1,lsh+n*2+1)-lsh-1;tr.build(1,1,len-1);for(int i=1; i<n*2; ++i){int ya=lower_bound(lsh+1,lsh+len+1,point[i].y1)-lsh;int yb=lower_bound(lsh+1,lsh+len+1,point[i].y2)-lsh;tr.update(1,ya,yb,point[i].id);ans=max(ans,tr.tr[1].maxn);}cout<<ans<<'\n';return 0;
}