题解：P4876 [USACO14MAR] The Lazy Cow G

· · 题解

The Lazy Cow G

平面上有若干点，要求在平面上任意地选出一个位置，使得到该点曼哈顿距离不超过 k 的点的数量最多。

首先题目要求的是曼哈顿距离。如果把对于一个位置曼哈顿距离不超过 k 的位置都标记出来，会发现是一个正方形旋转了 45^\circ。而对于这个图形，正方形是容易处理的，而旋转 45^\circ 不好操作，可以考虑将曼哈顿距离转换成切比雪夫距离，此处略微讲讲两距离及其转换。

曼哈顿距离：|x_i-x_j|+|y_i-y_j|。

切比雪夫距离：\max\{|x_i-x_j|, |y_i-y_j|\}。

可以发现，切比雪夫距离不超过 k 的图形就是一个边与 x 轴或 y 轴分别平行的一个正方形。

而对于曼哈顿距离，|x_i-x_j|+|y_i-y_j|=\max\{x_i-x_j, x_j-x_i\}+\max\{y_i-y_j, y_j-y_i\}=\max\{x_i-x_j+y_i-y_j, x_i-x_j+y_j-y_i, x_j-x_i+y_i-y_j, x_j-x_i+y_j-y_i\}=\max\{(x_i+y_i)-(x_j+y_j), (x_i-y_i)-(x_j-y_j), (x_j-y_j)-(x_i-y_i), (x_j+y_j)-(x_i+y_i)\}=\max\{|(x_i+y_i)-(x_j+y_j)|,|(x_i-y_i)-(x_j-y_j)|\}，则令 x'_i=x_i+y_i, y'_i=x_i-y_i，则上式等于 \max\{|x'_i-x'_j|, |y'_i-y'_j|\}。这样就完成了曼哈顿距离与切比雪夫距离的转换。

实际操作时，只需要先转换坐标，再按切比雪夫距离的求法做即可。

转换后，所求变为在平面上一个 2k\times2k 的矩形最多能覆盖的点数，这个用扫描线解决即可。

Code

#include <iostream>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <bitset>
#include <math.h>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define fst first
#define scd second
#define db double
#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector <int>
#define pii pair <int, int>
#define sz(x) ((int)x.size())
#define ms(f, x) memset(f, x, sizeof(f))
#define L(i, j, k) for (int i=(j); i<=(k); ++i)
#define R(i, j, k) for (int i=(j); i>=(k); --i)
#define ACN(i, H_u) for (int i=H_u; i; i=E[i].nxt)
using namespace std;
template <typename INT> void rd(INT &res) {
    res=0; bool f=false; char ch=getchar();
    while (ch<'0'||ch>'9') f|=ch=='-', ch=getchar();
    while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^48), ch=getchar();
    res=(f?-res:res);
}
template <typename INT, typename...Args>
void rd(INT &x, Args &...y) { rd(x), rd(y...); }
//dfs
const int inf=0x3f3f3f3f;
const int maxn=1e5;
const int N=maxn+10;
int n, kv, d[N], dcnt;
//wmr
#define ls (p<<1)
#define rs (p<<1|1)
struct SegmentTree { int l, r; ll ma, add; } t[N<<2];
void pushdown(int p) {
    t[ls].ma+=t[p].add;
    t[rs].ma+=t[p].add;
    t[ls].add+=t[p].add;
    t[rs].add+=t[p].add;
    t[p].add=0;
}
void pushup(int p) { t[p].ma=max(t[ls].ma, t[rs].ma); }
void build(int p, int l, int r) {
    t[p]={l, r, 0, 0};
    if (l==r) return;
    int mid=l+r>>1;
    build(ls, l, mid); build(rs, mid+1, r);
}
void update(int p, int l, int r, int k) {
    if (l<=t[p].l&&t[p].r<=r) return t[p].ma+=k, t[p].add+=k, void();
    int mid=t[p].l+t[p].r>>1; pushdown(p);
    if (l<=mid) update(ls, l, r, k);
    if (mid<r) update(rs, l, r, k);
    pushup(p);
}
ll query(int p, int l, int r) {
    if (l<=t[p].l&&t[p].r<=r) return t[p].ma;
    int mid=t[p].l+t[p].r>>1; pushdown(p); ll res=0;
    if (l<=mid) res=max(res, query(ls, l, r));
    if (mid<r) res=max(res, query(rs, l, r));
    return res;
}
struct node {
    int x, y, v;
    bool operator < (const node &k) const { return x<=k.x||x==k.x&&y<k.y; }
} a[N];
//incra

//lottle
signed main() {
//  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    rd(n, kv); kv<<=1;
    L(i, 1, n) {
        int v, x, y; rd(v, x, y);
        a[i].x=x+y, a[i].y=x-y, a[i].v=v; d[i]=a[i].y;
    }
    sort(a+1, a+n+1); sort(d+1, d+n+1); dcnt=unique(d+1, d+n+1)-d-1;
    L(i, 1, n) a[i].y=lower_bound(d+1, d+dcnt+1, a[i].y)-d;
    a[n+1].x=inf; int lst=0, cur=0; ll ans=0;
    build(1, 1, dcnt);
    L(i, 1, n) if (a[i].x!=a[i+1].x) {
        while (cur<n&&a[cur+1].x-a[i].x<=kv) ++cur, update(1, lower_bound(d+1, d+dcnt+1, d[a[cur].y]-kv)-d, a[cur].y, a[cur].v);
        ans=max(ans, t[1].ma);
        L(j, lst+1, i) update(1, lower_bound(d+1, d+dcnt+1, d[a[j].y]-kv)-d, a[j].y, -a[j].v);
        lst=i;
    }
    printf("%lld\n", ans);
    return 0;
}
/*
input
4 3
7 8 6
3 0 0
4 6 0
1 4 2
output
8
*/