线段树优化建图

· · 个人记录

今天第一次做线段树优化建图的题，来源是Zyingyzzz的比赛 T3。

题意：将区间 [l_1,r_1] 与区间 [l_2,r_2] 建边，求编号为 1 的点到各个点的最短路。如没有路径输出-1。0\leq n,m\leq2e5。

正文

0x01 暴力做法

看到这题，第一眼思路是暴力。暴力给区间 [l_1,r_1] 与 [l_2,r_2]直接建边。复杂度显然达到了 O(mn^2)，超时 。拿下 30 分。于是花了十几分钟打了个dijsktra的模板。打这个部分分也作与验证dijsktra写的是否正确吧。

注意的细节是，可能有重边，所以要先用邻接矩阵存完再放到邻接表里。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7+5;
int fir[maxn],to[maxn],nxt[maxn],w[maxn],tot,ji[1005][1005];
void add(int x,int y,int z){
    to[++tot]=y;
    nxt[tot]=fir[x];
    w[tot]=z;
    fir[x]=tot;
}
int dis[maxn];
int m,n,pb,pa1,pa2,x,y,z,ans;
bool vis[maxn];
struct data{int x,dis;};
bool operator < (data a,data b){
    return a.dis>b.dis;
}
priority_queue<data> q;
void dijkstra(int s){
    for(int i=1;i<=n;i++)dis[i]=(i==s?0:1e9);
    memset(vis,1,sizeof vis);
    q.push({s,0});
    while(!q.empty()){
        int x=q.top().x;
        q.pop();
        if(!vis[x])continue;
        vis[x]=false;
        for(int i=fir[x];i;i=nxt[i]){
            int y=to[i],z=w[i];
            if(z+dis[x]<dis[y]){
            dis[y]=dis[x]+z;
            q.push({y,dis[y]});
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=1000;i++)for(int j=1;j<=1000;j++)ji[i][j]=(i==j?0:1e9);
    for(int l1,r1,l2,r2,w,i=1;i<=m;i++){
        scanf("%d%d%d%d%d",&l1,&r1,&l2,&r2,&w);
        for(int j=l1;j<=r1;j++){
            for(int k=l2;k<=r2;k++){
                ji[j][k]=min(ji[j][k],w);
            }
        }
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
        if(ji[i][j]!=1e9&&ji[i][j])add(i,j,ji[i][j]);
    }
    dijkstra(1);
    for(int i=1;i<=n;i++)printf("%d\n",(dis[i]==1e9?-1:dis[i]));
    return 0;
}

注意到了区间二字，于是思考是否有方法优化建图。

0x02 线段树单点优化

考虑线段树建图。将节点如线段树放置（图片来源 ）：

复制这个序列入线段树，然后在将外界序列的元素与线段树中的元素连边。

注意到，原本是需要连 n 个节点的，现在却只需要连 \log n 个节点。跑最短路时直接使用外界序列与内界的连边即可。时间复杂度从原来的 O(mn^2) 降为 O(mn\log n)。

那么我们需要对线段树做什么操作？

目标：实现当前节点与左右儿子有一条边权为 0 的边，并对线段树数组a进行赋值。

inline void build(int rt,int l,int r){
    if(l==r){a[l]=rt;return ;}
    int mid=l+r>>1;
    add(rt,rt<<1,0),add(rt,rt<<1|1,0);
    build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
    return ;
}

目标：实现序列数与当前线段树上节点连边。

注意细节：因为线段树上也会有连边占用邻接表空间，所以外界序列节点需要加上maxm（即 4 倍的 n）。

inline void change(int rt,int l,int r,int ql,int qr,int x,int v){
    if(ql<=l&&r<=qr){
        add(a[x]+maxm,rt,v);
        return ;
    }
    int mid=l+r>>1;
    if(ql<=mid)change(rt<<1,l,mid,ql,qr,x,v);
    if(qr>mid)change(rt<<1|1,mid+1,r,ql,qr,x,v);
    return ;
}

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7+5,maxm=8e5+5;
int fir[maxn],to[maxn],nxt[maxn],w[maxn],tot,a[maxn];
inline void add(int x,int y,int z){
    to[++tot]=y;
    nxt[tot]=fir[x];
    w[tot]=z;
    fir[x]=tot;
}
int dis[maxn];
int m,n,pb,pa1,pa2,x,y,z,ans;
bool vis[maxn];
struct data{int x,dis;};
bool operator < (data a,data b){
    return a.dis>b.dis;
}
priority_queue<data> q;
inline void build(int rt,int l,int r){
    if(l==r){a[l]=rt;return ;}
    int mid=l+r>>1;
    add(rt,rt<<1,0),add(rt,rt<<1|1,0);
    build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
    return ;
}
inline void change(int rt,int l,int r,int ql,int qr,int x,int v){
    if(ql<=l&&r<=qr){
        add(a[x]+maxm,rt,v);
        return ;
    }
    int mid=l+r>>1;
    if(ql<=mid)change(rt<<1,l,mid,ql,qr,x,v);
    if(qr>mid)change(rt<<1|1,mid+1,r,ql,qr,x,v);
    return ;
}
inline void dijkstra(int s){
    for(int i=1;i<=1e7;i++)dis[i]=1e9;
    dis[s]=0;
    memset(vis,1,sizeof vis);
    q.push({s,0});
    while(!q.empty()){
        int x=q.top().x;
        q.pop();
        if(!vis[x])continue;
        vis[x]=false;
        for(int i=fir[x];i;i=nxt[i]){
            int y=to[i],z=w[i];
            if(z+dis[x]<dis[y]){
            dis[y]=dis[x]+z;
            q.push({y,dis[y]});
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    build(1,1,n);
    for(int i=1;i<=n;i++)add(a[i],a[i]+maxm,0),add(a[i]+maxm,a[i],0);//叶子结点与自己建边
    for(int l1,r1,l2,r2,vl,i=1;i<=m;i++){
        scanf("%d%d%d%d%d",&l1,&r1,&l2,&r2,&vl);
        for(int j=l1;j<=r1;j++){
            change(1,1,n,l2,r2,j,vl);
        }
    }
    dijkstra(a[1]+maxm);
    for(int i=1;i<=n;i++)printf("%d\n",(dis[a[i]]==1e9?-1:dis[a[i]]));
    return 0;
}

然而，线段树常数巨大，导致最终只跑过了sub2包的两个点。分数依旧为 30。还有些细节在代码里有注释。

0x03 暴力分解线段树节点建边

这个算法不是我想的，是我AC此题问Zyingyzzz 60 分的做法得知的。这个做法是 O(m\log^2n) 的。

暴力建两棵线段树，对每个区间 \log n 建边，最终建边复杂度达到O(mlog^2n)。

0x04 考虑建立 0 点

考虑对 O(nmlogn)（因为我当时是直接考虑对这个复杂度优化）继续优化，当时第一步是想到可以建立 0 点存储各边关系。但这个解法是错误的。原因在于顺序无法确立。但这个错误的思路助于了我思考最终解法。

0x05 考虑建立虚拟点

我们发现，对一段区间与另一段区间建边的问题可以转化为：将一段区间的边入到一个虚拟点上，再将这个虚拟点入到各个点上。各个操作的时间复杂度竟然是 logn 的，于是就能以 O(m\log n)的优秀复杂度通过此题。

不难发现，操作无非是对 0x02 的操作多加了个 change2 为一个点对一个区间入边的操作，并将 build 稍作修改。

多加一条左右儿子与父亲的连边。因为要考虑往下传递。代码如下：

add((rt<<1)+maxm,rt+maxm,0),add((rt<<1|1)+maxm,rt+maxm,0);

值得一提的是，边权如何保证呢？

一开始考虑将边权除以 2，给每条节点一半的权值，显然不好维护，最后考虑给入虚拟节点的边赋边权为 w，出的赋为 0。

另外，考虑到序列最多又能产生 n 个节点，也即 n\times 4 条边（对线段树内 2\times n+1 个节点都连一条入，再连一条出），加上先前的点，于是需要将数枚举到 8\times n。

相比于 change1，这个函数无非就是将建边反过来而已。代码如下：

inline void change2(int rt,int l,int r,int ql,int qr,int x,int v){
    if(ql<=l&&r<=qr){
        add(rt+maxm,x,v);
        return ;
    }
    int mid=l+r>>1;
    if(ql<=mid)change2(rt<<1,l,mid,ql,qr,x,v);
    if(qr>mid)change2(rt<<1|1,mid+1,r,ql,qr,x,v);
    return ;
}

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7+5,maxm=8e5+5,MAXM=1e6+6e5+5;
int fir[maxn],to[maxn],nxt[maxn],w[maxn],tot,a[maxn];
inline void add(int x,int y,int z){
    to[++tot]=y;
    nxt[tot]=fir[x];
    w[tot]=z;
    fir[x]=tot;
}
int dis[maxn];
int m,n,pb,pa1,pa2,x,y,z,ans;
bool vis[maxn];
struct data{int x,dis;};
bool operator < (data a,data b){
    return a.dis>b.dis;
}
priority_queue<data> q;
inline void build(int rt,int l,int r){
    if(l==r){a[l]=rt;return ;}
    int mid=l+r>>1;
    add(rt,rt<<1,0),add(rt,rt<<1|1,0);
    add((rt<<1)+maxm,rt+maxm,0),add((rt<<1|1)+maxm,rt+maxm,0);
    build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
    return ;
}
inline void change1(int rt,int l,int r,int ql,int qr,int x){
    if(ql<=l&&r<=qr){
        add(x,rt,0);//+maxm
        return ;
    }
    int mid=l+r>>1;
    if(ql<=mid)change1(rt<<1,l,mid,ql,qr,x);
    if(qr>mid)change1(rt<<1|1,mid+1,r,ql,qr,x);
    return ;
}
inline void change2(int rt,int l,int r,int ql,int qr,int x,int v){
    if(ql<=l&&r<=qr){
        add(rt+maxm,x,v);
        return ;
    }
    int mid=l+r>>1;
    if(ql<=mid)change2(rt<<1,l,mid,ql,qr,x,v);
    if(qr>mid)change2(rt<<1|1,mid+1,r,ql,qr,x,v);
    return ;
}
inline void dijkstra(int s){
    for(int i=1;i<=1e7;i++)dis[i]=1e9;
    dis[s]=0;
    memset(vis,1,sizeof vis);
    q.push({s,0});
    while(!q.empty()){
        int x=q.top().x;
        q.pop();
        if(!vis[x])continue;
        vis[x]=false;
        for(int i=fir[x];i;i=nxt[i]){
            int y=to[i],z=w[i];
            if(z+dis[x]<dis[y]){
            dis[y]=dis[x]+z;
            q.push({y,dis[y]});
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    build(1,1,n);
    for(int i=1;i<=n;i++)add(a[i],a[i]+maxm,0),add(a[i]+maxm,a[i],0);
    for(int l1,r1,l2,r2,vl,i=1;i<=m;i++){
        scanf("%d%d%d%d%d",&l1,&r1,&l2,&r2,&vl);
        change2(1,1,n,l1,r1,MAXM+i,vl);
        change1(1,1,n,l2,r2,MAXM+i);
    }
    dijkstra(a[1]+maxm);
    for(int i=1;i<=n;i++)printf("%d\n",(dis[a[i]]==1e9?-1:dis[a[i]]));
    return 0;
}

0x06 巩固

继续探寻几道类似于这道 T3的题。

P6348 Journeys 模板