专栏文章

题解：P5193 [TJOI2012] 炸弹

ZZilljy258
P5193题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@min5ruib
此快照首次捕获于
2025/12/01 21:01
3 个月前
此快照最后确认于
2025/12/01 21:01
3 个月前
查看原文
这是一篇使用平衡树做法实现的题解。
此题代码我是直接从 P2960 粘过来的哈哈。
首先对将曼哈顿距离限制转化为切比雪夫距离限制。
∣x1−x2∣+∣y1−y2∣≤C \lvert x_1 - x_2 \rvert + \lvert y_1 - y_2 \rvert \leq C
等价于：
{∣x1−x2+y1−y2∣≤C∣x1−x2+y2−y1∣≤C \left\{ \begin{aligned} \lvert x_1 - x_2 + y_1 - y_2 \rvert \leq C \\ \lvert x_1 - x_2 + y_2 - y_1 \rvert \leq C \end{aligned} \right.
进而得到：
{∣∣x1+y1∣−∣x2+y2∣∣≤C∣∣x1−y1∣−∣x2−y2∣∣≤C \left\{ \begin{aligned} \left\lvert \lvert x_1 + y_1 \rvert - \lvert x_2 + y_2 \rvert \right\rvert \leq C \\ \left\lvert \lvert x_1 - y_1 \rvert - \lvert x_2 - y_2 \rvert \right\rvert \leq C \end{aligned} \right.
设计一个切比雪夫坐标系中的点 (x′,y′)=(x+y,x−y)(x',y')=(x+y,x-y) 来对应原来的点，使两点间的距离限制变为 max⁡(∣x1′−x2′∣,∣y1′−y2′∣)≤C\max(\lvert x'_1-x'_2\rvert,\lvert y'_1-y'_2 \rvert) \leq C。
那么接下来只需要对点进行排序，用数据结构维护即可。
具体实现方法：
  1. 对所有转化后的点按照横坐标排序。
  2. 队列维护横坐标，保证队列内的所有点与当前点横坐标之差小于等于 CC。
  3. 平衡树或 set 关联容器在值域上维护纵坐标，每次找到队列中纵坐标距离当前点恰好小于等于 CC 的两个点并使用并查集将这三个点合并。
关于最后一条为什么只需要合并距离恰好小于等于 CC 的两个点，考虑反证法。（以下“距离”皆表示纵坐标差，由于是纵坐标距离，所以枚举与合并的顺序对证明没有影响）
假设目前枚举到点 ii，队列中存在点 jj 可合并，距离 ii 恰好小于等于 CC 的点为 kk，满足 yi≤yj≤yk≤yi+Cy_i \leq y_j \leq y_k \leq y_i + C（大于等于同理），且 jj 不会与 ii 和 kk 合并。
那么存在一个点 k2≠kk_2 \neq k 满足 k2k_2 距离 jj 恰好小于等于 CC。
此时可以发现，我们得到了一组新的 i′i'，j′j'，k′k' 为
{i′=jj′=kk′=k2 \left\{ \begin{aligned} i' &= j \\ j' &= k \\ k' &= k2 \end{aligned} \right.
以此类推，得到的点集不是一个有限集合，与题目矛盾。
可以理解为一个社区中必然存在一个最大或最小纵坐标，他会与所有距离他小于等于 CC 点直接合并，并将这些分裂的点集合并。
最后放一下代码。
注意几个小细节，都在代码里标注了。
CPP
#include<iostream>
#include<cstdio>
#include<algorithm>
#define lo (t[nw].lson)
#define ro (t[nw].rson)

using namespace std;

const int N=1e5+10;

int n;
int fa[N];
long long C;
struct Node{
    long long x,y;
    bool operator<(const Node&tmp){

        return x<tmp.x;
    }
}a[N];

struct Tree{
    long long key;
    long long val;
    int id;
    int sz;
    int lson,rson;
}t[N<<2];

int tot_node=0;
int mkrd(long long x,int id){
    ++tot_node;
    t[tot_node].key=x;
    t[tot_node].val=rand();
    t[tot_node].sz=1;
    t[tot_node].id=id;
    return tot_node;
}

void upd(int nw){
    t[nw].sz=t[lo].sz+t[ro].sz+1;
    return ;
}

void split_key(int nw,long long x,int z,int &l,int &r){
    if(!nw){
        l=r=0;
        return ;
    }

    if(t[nw].key<x){
        l=nw;
        split_key(ro,x,z,ro,r);
    }
    else if(t[nw].key>x){
        r=nw;
        split_key(lo,x,z,l,lo);
    }
    else{
        if(t[nw].id<=z||!z){
            l=nw;
            split_key(ro,x,z,ro,r);
        }
        else{
            r=nw;
            split_key(lo,x,z,l,lo);
        }
    }

    upd(nw);

    return ;
}

void split_sz(int nw,int x,int &l,int &r){
    if(!nw){
        l=r=0;
        return ;
    }

    if(t[lo].sz+1<=x){
        l=nw;
        split_sz(ro,x-t[lo].sz-1,ro,r);
    }
    else{
        r=nw;
        split_sz(lo,x,l,lo);
    }
    upd(nw);

    return ;
}

int merge(int l,int r){
    if(!l||!r){
        return l|r;
    }

    int nw;
    if(t[l].val<=t[r].val){
        nw=l;
        ro=merge(ro,r);
    }
    else{
        nw=r;
        lo=merge(l,lo);
    }
    upd(nw);
    return nw;
}

int rt,dl,dr,tmp;

void Insert(long long x,int z){
    split_key(rt,x,z,dl,dr);
    dl=merge(dl,mkrd(x,z));
    rt=merge(dl,dr);
    return ;
}

void Delete(long long x,int z){
    split_key(rt,x,z,dl,dr);
    split_sz(dl,t[dl].sz-1,dl,tmp);
    rt=merge(dl,dr);
    return ;
}

int Query(long long x,int op){
//op：
//0 表示小于等于 x（实际求得最后一个小于等于 x 的数字）
//1 表示大于 x（实际求得第一个大于 x 的数字）
    int ans=0;
    split_key(rt,x,0,dl,dr);
    if(op==0){
        split_sz(dl,t[dl].sz-1,dl,tmp);
        ans=t[tmp].id;
        dl=merge(dl,tmp);
    }
    else{
        split_sz(dr,1,tmp,dr);
        ans=t[tmp].id;
        dr=merge(tmp,dr);
    }
    rt=merge(dl,dr);
    return ans;
}

int find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}

int blk[N];

int main(){
    // freopen("/run/media/zilljy/Dear Sir/Study/Vjudge/数据结构训练（一）树状数组+线段树/P2906_2.in","r",stdin);

    srand(2587706597);//加我QQ

    scanf("%d%lld",&n,&C);

    for(int i=1;i<=n;++i){
        scanf("%lld%lld",&a[i].x,&a[i].y);
        a[i].x=a[i].x+a[i].y;
        a[i].y=a[i].x-(a[i].y<<1);//转切比雪夫坐标系
        fa[i]=i;
    }

    sort(a+1,a+n+1);

    int p=1;
    for(int i=1;i<=n;++i){
        while(p<i&&a[i].x-a[p].x>C){//维护横坐标
            Delete(a[p].y,p);
            ++p;
        }
        long long up=a[i].y+C;
        long long dn=a[i].y-C-1;//大于这个数减一，否则如果没有这个数值，会向下越界。

        int u=Query(up,0);
        int v=Query(dn,1);

        // cout<<u<<" "<<v<<endl;
        if(u&&a[u].y-a[i].y<=C&&a[i].y-a[u].y<=C){//此处进行边界判断，防止找不到这样的数而越界或者返回错误值，下同。
            u=find(u);
            fa[u]=i;
        }
        if(v&&a[i].y-a[v].y<=C&&a[v].y-a[i].y<=C){
            v=find(v);
            fa[v]=i;
        }


        Insert(a[i].y,i);
    }

    int num=0;
    for(int i=1;i<=n;++i){
        if(fa[i]==i) ++num; //统计社区数量
    }

    printf("%d",num);

    return 0;
}
是不是一份非常优雅的代码呢？

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...