解题报告二维数点

紫钦 · 2023-02-05 15:51:21 · 个人记录

题目链接：二维数点。

题目大意

给你一张 n 个点 m 条边的无向图，边有边权 w_i，点有点权 c_i。友好点对定义为满足点权差 \geqslant L 的无序点对。两点间的最短距离定义为两点间所有路径中最大边权值的最小值。求所有友好点对之间的最短距离之和。

数据规模：1\leqslant n\leqslant2\times10^5，1\leqslant m\leqslant4\times10^5，1\leqslant w_i,L\leqslant10^8，0\leqslant c_i\leqslant10^8。

样例输入

样例输出

解法：Kruskal 重构树+某种启发式+二维数点

“最短距离定义为两点间所有路径中最大边权值的最小值”告诉我们，要求出 Kruskal 重构树。

对重构树 dfs，记录 dfs 序以及每个点子树在 dfs 序上的起止点。

有了重构树，就可以知道所有点对之间的最短距离之和。我们再减去所有非友好点对之间的最短距离即可。

对每一个 Kruskal 新建的点，其对答案的贡献为：遍历左子树所有点 i，查询右子树 [c_i-L+1, c_i+L-1] 范围内的点的数量。右子树的 dfs 序连续，所以问题转化为二维数点。

但是左子树的点可能很多，所以比较左右子树大小。左子树小，就遍历左子树内每一个点，新建一个对右子树的二维数点查询；如果右子树小，就遍历右子树内每一个点，新建一个对左子树的二维数点查询。这样查询的总次数是 O(n\log_2n) 级别的。

注意事项

不用离散化，因为纵坐标是 dfs 序，横坐标是点权，所以二维数点按横坐标拆开排序就好。
看起来常数就巨大。
时间复杂度 O(n\log_2^2n)。

AC 代码

评测记录

（居然只有一个测试点）

#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 200005
#define MAXM 400005
#define lowbit(x) ((x)&(-(x)))
using namespace std;
int tot,cnt1,cnt2,c[MAXN],dfn[MAXN],b[MAXN];
int f[MAXN<<1],val[MAXN<<1],ls[MAXN<<1],rs[MAXN<<1],l[MAXN<<1],r[MAXN<<2];
long long ans;
struct Edge {
    int x,y,w;
}e[MAXM];
struct Dot {
    int x,y;
    Dot(int _x=0,int _y=0):x(_x),y(_y) {}
}dot[MAXN];
struct Que {
    int x,l,r,type,id;
    Que(int _x=0,int _l=0,int _r=0,int _type=0,int _id=0):x(_x),l(_l),r(_r),type(_type),id(_id) {}
}que[(MAXN<<4)+(MAXN<<2)];
bool cmp(Edge a,Edge b) {return a.w<b.w;}
bool cmp1(Dot a,Dot b) {return a.x<b.x;}
bool cmp2(Que a,Que b) {return a.x<b.x;}
int getf(int x) {return f[x]<0?x:f[x]=getf(f[x]);}
void Kruskal(int n,int m) {
    sort(e+1,e+m+1,cmp);
    memset(f,0xff,(n+1)*sizeof(int));
    n=(n<<1)-1;
    for(int i=1,x,y,tot=(n+1)>>1;i<=m && tot<=n;++i) {
        if((x=getf(e[i].x))==(y=getf(e[i].y))) continue;
        f[++tot]=f[x]+f[y];
        val[tot]=e[i].w;
        if(f[x]>=f[y]) ls[tot]=x, rs[tot]=y; // left son must be smaller.
        else ls[tot]=y, rs[tot]=x;
        f[x]=f[y]=tot;
    }
}
void dfs(int x,int L) {
    l[x]=tot+1;
    if(!ls[x]) {
        dfn[++tot]=x;
        r[x]=tot;
        dot[++cnt1]=Dot(c[x],tot);
        return;
    }
    dfs(ls[x],L);
    dfs(rs[x],L);
    r[x]=tot;
    ans+=(long long)val[x]*(r[ls[x]]-l[ls[x]]+1)*(r[rs[x]]-l[rs[x]]+1);
    for(int i=l[ls[x]];i<=r[ls[x]];++i) {
        que[++cnt2]=Que(c[dfn[i]]-L,l[rs[x]],r[rs[x]],-1,x);
        que[++cnt2]=Que(c[dfn[i]]+L-1,l[rs[x]],r[rs[x]],1,x);
    }
}
void add(int x,int v,int n) {
    for(;x<=n;x+=lowbit(x)) b[x]+=v;
}
int query(int x) {
    int ans=0;
    for(;x;x-=lowbit(x)) ans+=b[x];
    return ans;
}
int read() {
    char ch=getchar(); int x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=(x*10)+(ch^48),ch=getchar();
    return x;
}
int main()
{
    int n,m,L;
    n=read(); m=read(); L=read();
    for(int i=1;i<=n;++i) c[i]=read();
    for(int i=1;i<=m;++i) e[i].x=read(), e[i].y=read(), e[i].w=read();
    Kruskal(n,m);
    dfs((n<<1)-1,L);
    sort(dot+1,dot+cnt1+1,cmp1);
    sort(que+1,que+cnt2+1,cmp2);
    for(int i=1,j=1;i<=cnt2;++i) {
        while(j<=n && dot[j].x<=que[i].x) add(dot[j].y,1,n), ++j;
        ans-=(long long)val[que[i].id]*que[i].type*(query(que[i].r)-query(que[i].l-1));
    }
    printf("%lld",ans);
    return 0;
}

解题报告 二维数点