自动搬运

查看原文

来自洛谷，原作者为

	cccgift AFO

搬运于2025-08-24 22:04:49，当前版本为作者最后更新于2019-06-30 20:31:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看到本题没有题解，于是来发一篇。

本题的题意是在平面上找到一个点，使距离这个点的曼哈顿距离不超过$k$的牧草数最大化。

我们把曼哈顿距离不超过$k$的图像画出来，发现它长这样：

看着特别不爽，根本不好处理。

但是，如果我们能够让它长这样：

那么，就可以使用扫描线来维护，从而做到$O(nlogn)$了。

我们把这两个图联系一下，看过洛谷日报#182 常用距离算法详解的都应该发现，这不就是曼哈顿距离转切比雪夫距离吗？

于是，我们就可以把坐标$(x,y)$读入后，令它新的坐标$(X,Y)$为$(x+y,x-y)$，问题就转化成了P1502 窗口的星星了。

当然，还有一些细节处理：

1、最好把新的坐标离散化，因为$x-y$可能是负数。

2、我们可以发现，转化后的正方形的边长是$2k$的，处理时要小心。

3、注意！如果有高度相同的两条边，一定要先处理下边（也就是加进去的边），因为如果有这种情况，同时在这两条边上的点的答案会被记录到两条边中，但是如果先处理上边，就只会被记录到一条边中，导致答案出错！这样，我们会得到样例没过却有81分的好成绩。

Update：原来代码的读入压行了，这里把它展开。

代码如下：

#include<cstdio>
#include<cstring>
#include<cctype>
#include<utility>
#include<algorithm>
using namespace std;
#define res register int
//#define cccgift
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) //fread优化
char buf[1<<21],*p1=buf,*p2=buf;
namespace wode{
    template<typename T>
    inline void read(T &x) //快读
    {
        static char ch;bool f=1;
        for(x=0,ch=getchar();!isdigit(ch);ch=getchar()) if(ch=='-') f=0;
        for(;isdigit(ch);x=(x<<1)+(x<<3)+(ch^48),ch=getchar());x=f?x:-x;
    }
    template<typename T>
    inline T max(T x,T y) {return x<y?y:x;}
    template<typename T>
    inline T min(T x,T y) {return x<y?x:y;}
    template<typename T>
    inline void chkmax(T &x,T y) {x=x<y?y:x;}
    template<typename T>
    inline void chkmin(T &x,T y) {x=x<y?x:y;}
}
using wode::read;using wode::chkmin;using wode::chkmax;
struct node{
    int x,y,z,k;
    bool operator <(const node &b)const {return x<b.x||(x==b.x&&k>b.k);} //先处理下边！
} a[200001];
int tot,dat[800001],ad[800001],len,b[200001],n,m,w,h,nn,t,xx,yy,k;
inline void spread(int q) {
    if(ad[q]) {
        ad[q<<1]+=ad[q],ad[q<<1|1]+=ad[q];
        dat[q<<1]+=ad[q],dat[q<<1|1]+=ad[q];
        ad[q]=0;
    }
}
void change(int q,int l1,int r1,int l,int r,int k) {
    if(r<l1||r1<l) return;
    if(l<=l1&&r1<=r) {dat[q]+=k,ad[q]+=k;return;}
    int mid=l1+r1>>1;spread(q);
    change(q<<1,l1,mid,l,r,k),change(q<<1|1,mid+1,r1,l,r,k),dat[q]=wode::max(dat[q<<1],dat[q<<1|1]);
}
int main()
{
    read(n),read(k),k<<=1;
    for(res i=1;i<=n;++i) {
    	read(a[++len].k),read(xx),read(yy);
		a[len].x=xx+yy,a[len].y=xx-yy;
		b[len]=a[len].y;
		++len,a[len].x=a[len-1].x+k,a[len].y=a[len-1].y;
		b[len]=a[len].z=a[len-1].z=a[len-1].y+k;
		a[len].k=-a[len-1].k;
	}
//	for(res i=1;i<=len;++i) printf("%d %d %d %d\n",a[i].k,a[i].x,a[i].y,a[i].z);
    sort(b+1,b+1+len),nn=unique(b+1,b+1+len)-b-1;
//	for(res i=1;i<=nn;++i) printf("%d ",b[i]);puts("");
    for(res i=1;i<=len;++i) a[i].y=lower_bound(b+1,b+1+nn,a[i].y)-b,a[i].z=lower_bound(b+1,b+1+nn,a[i].z)-b; //把坐标离散化
//	for(res i=1;i<=len;++i) printf("%d %d\n",a[i].y,a[i].z);
    sort(a+1,a+1+len);
    for(res i=1;i<=len;++i) change(1,1,nn,a[i].y,a[i].z,a[i].k),chkmax(tot,dat[1]); //最后的答案就是每一次扫描的最大值，详见窗口的星星那道题。
    printf("%d\n",tot);
    return 0;
}