P7561 [JOISC 2021] 道路の建設案 (Road Construction) (Day2) 题解

hzoi_Shadow · 2025-03-30 09:59:30 · 题解

题目传送门

前置知识

K-D Tree

解法

观察到所求是一个邻域查询的形式，尝试使用 KD-Tree，但需注意最坏时间复杂度并不正确（因为本题数据稍弱所以可以通过）。

同 luogu P2093 [国家集训队] JZPFAR，不妨开一个大小为 2k 的堆加入答案时不断和堆顶比较，在输出答案时跳着取答案。

启发式搜索时估价函数取到子矩形的最近距离即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
const ll inf=0x7f7f7f7f7f7f7f7f;
struct node
{
    int pos[2];
}a[250010];
int cur,cnt=0;
ll ans[250010];
priority_queue<ll>q;
bool cmp(node x,node y)
{
    return x.pos[cur]<y.pos[cur];
}
ll get_dis(int x,int y)
{
    return llabs(a[x].pos[0]-a[y].pos[0])+llabs(a[x].pos[1]-a[y].pos[1]);
}
struct KDT
{
    int root;
    struct kd_tree
    {
        int ls,rs,pos[2],mx[2],mn[2];
    }tree[250010];
    #define lson(rt) (tree[rt].ls)
    #define rson(rt) (tree[rt].rs)
    int build_rt(int id)
    {
        int rt=id;
        lson(rt)=rson(rt)=0;
        for(int i=0;i<=1;i++)
            tree[rt].pos[i]=tree[rt].mx[i]=tree[rt].mn[i]=a[id].pos[i];
        return rt;
    }
    void pushup(int rt)
    {
        for(int i=0;i<=1;i++)
        {
            tree[rt].mx[i]=tree[rt].mn[i]=tree[rt].pos[i];
            if(lson(rt)!=0)
            {
                tree[rt].mx[i]=max(tree[rt].mx[i],tree[lson(rt)].mx[i]);
                tree[rt].mn[i]=min(tree[rt].mn[i],tree[lson(rt)].mn[i]);
            }
            if(rson(rt)!=0)
            {
                tree[rt].mx[i]=max(tree[rt].mx[i],tree[rson(rt)].mx[i]);
                tree[rt].mn[i]=min(tree[rt].mn[i],tree[rson(rt)].mn[i]);
            }
        }
    }
    void build(int &rt,int l,int r,int dir)
    {
        int mid=(l+r)/2;  cur=dir;
        nth_element(a+l,a+mid,a+r+1,cmp);  rt=build_rt(mid);
        if(l<=mid-1)  build(lson(rt),l,mid-1,dir^1);
        if(mid+1<=r)  build(rson(rt),mid+1,r,dir^1);
        pushup(rt);
    }
    ll cost(int rt,int pos)
    {
        ll ans=0;
        for(int i=0;i<=1;i++)
        {
            if(a[pos].pos[i]<tree[rt].mn[i])  ans+=tree[rt].mn[i]-a[pos].pos[i];
            if(a[pos].pos[i]>tree[rt].mx[i])  ans+=a[pos].pos[i]-tree[rt].mx[i];
        }
        return ans;
    }
    void query(int rt,int l,int r,int pos)
    {
        int mid=(l+r)/2;
        if(rt!=pos&&get_dis(rt,pos)<q.top())
        {
            q.pop();  q.push(get_dis(rt,pos));
        }
        ll fl=((l<=mid-1)?cost(lson(rt),pos):inf);
        ll fr=((mid+1<=r)?cost(rson(rt),pos):inf); 
        if(fl<q.top()&&fr<q.top())
        {
            if(fl<fr)
            {
                query(lson(rt),l,mid-1,pos);
                if(fr<q.top())  query(rson(rt),mid+1,r,pos);
            }
            else
            {
                query(rson(rt),mid+1,r,pos);
                if(fl<q.top())  query(lson(rt),l,mid-1,pos);
            }
        }
        else  if(fl<q.top())  query(lson(rt),l,mid-1,pos);
        else  if(fr<q.top())  query(rson(rt),mid+1,r,pos);
    }
}K;
int main()
{
// #define Isaac
#ifdef Isaac
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    int n,k,i;
    cin>>n>>k;  k*=2;
    for(i=1;i<=n;i++)  cin>>a[i].pos[0]>>a[i].pos[1];
    for(i=1;i<=k;i++)  q.push(inf);
    K.build(K.root,1,n,0);
    for(i=1;i<=n;i++)  K.query(K.root,1,n,i);
    for(i=k;i>=1;i--)
    {
        ans[i]=q.top();  q.pop();
    }
    for(i=1;i<=k;i+=2)  cout<<ans[i]<<endl;
    return 0;
}