P4876 The Lazy Cow G 非常神奇有意思
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|1
struct 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;
}
浙公網安備 33010602011771號