题解：P5193 [TJOI2012] 炸弹

Zilljy258 · 2025-11-18 14:17:24 · 题解

这是一篇使用平衡树做法实现的题解。

此题代码我是直接从 P2960 粘过来的哈哈。

首先对将曼哈顿距离限制转化为切比雪夫距离限制。

等价于：

进而得到：

设计一个切比雪夫坐标系中的点 (x',y')=(x+y,x-y) 来对应原来的点，使两点间的距离限制变为 \max(\lvert x'_1-x'_2\rvert,\lvert y'_1-y'_2 \rvert) \leq C。

那么接下来只需要对点进行排序，用数据结构维护即可。

具体实现方法：

1. 对所有转化后的点按照横坐标排序。
2. 队列维护横坐标，保证队列内的所有点与当前点横坐标之差小于等于 C。
3. 平衡树或 set 关联容器在值域上维护纵坐标，每次找到队列中纵坐标距离当前点恰好小于等于 C 的两个点并使用并查集将这三个点合并。

关于最后一条为什么只需要合并距离恰好小于等于 C 的两个点，考虑反证法。（以下“距离”皆表示纵坐标差，由于是纵坐标距离，所以枚举与合并的顺序对证明没有影响）

假设目前枚举到点 i，队列中存在点 j 可合并，距离 i 恰好小于等于 C 的点为 k，满足 y_i \leq y_j \leq y_k \leq y_i + C（大于等于同理），且 j 不会与 i 和 k 合并。

那么存在一个点 k_2 \neq k 满足 k_2 距离 j 恰好小于等于 C。

此时可以发现，我们得到了一组新的 i'，j'，k' 为

以此类推，得到的点集不是一个有限集合，与题目矛盾。

可以理解为一个社区中必然存在一个最大或最小纵坐标，他会与所有距离他小于等于 C 点直接合并，并将这些分裂的点集合并。

最后放一下代码。

注意几个小细节，都在代码里标注了。

#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;
}

是不是一份非常优雅的代码呢？