P4876 [USACO14MAR] The Lazy Cow_Gold 懒惰的牛(金)

· · 题解

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

本题的题意是在平面上找到一个点，使距离这个点的曼哈顿距离不超过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;
}