BZOJ3073 [Pa2011]Journeys[最短路—线段树优化建边]

新技能get✔。

线段树优化建边主要是针对一类连续区间和连续区间之间建边的题，建边非常的优秀。。

---

这题中，每次要求$[l1,r1]$每一点向$[l2,r2]$每一点建无向边，然后单元最短路。

---

暴力建边，边数$O(n^2m)$，时空双炸。

优化一点的建边，对于一个区间的点，把他们统一向一个虚点连零边，再从这个虚点向另一个区间每一个点连一条带权边。这样，每一条路径都是可以通过这个来表示的。边数$O(nm)$，仍然不行。

然后，采用线段树的优秀的“将区间拆分成不超过$log n$个小区间”的性质，对于$n$个点，建两颗线段树$A,B$，$A$称作入树，$B$称作出树。他们的叶子就是所有的$n$个点，上面的非叶点就是区间。。（先假设是单向的边）然后，对于一次区间向另一区间的连边，从出树$B$拆分出来的对应的$log n$个区间代表的点分别向一个新开的虚点连一条有向0边，再从这个虚点向入树$A$对应的另一个区间拆分的若干小区间点连带权边，这样实现了区间连边。但是，这只是区间整体连边了，还要保证点与点连通，只要把出树$B$每个点从孩子向父亲连有向0边，入树$A$每个点从父亲向孩子连有向0边，就表示一个点通过“爬”到一个区间点，走过虚点，在下来走到另外一个目标点这样一个过程。最后，走进入树后，为了可以继续走，从$A$向$B$的每一个代表相同区间的点连0边，表示再过去。

有一个dalao的图可能会解释的非常清晰。。附上地址

线段树优化建边大致就是这个原理。然后直接从底层叶子开始为源点跑dij就行了。

然后个人觉得很多代码很繁。。偶尔看到一种写法，对每个点编一个号，把AB两树底层叶子编号直接合并成一个，省去了两树之间的相互建边。。这样码量就小很多了。具体还是看代码。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define mst(x) memset(x,0,sizeof x)
#define dbg(x) cerr << #x << " = " << x <<endl
#define dbg2(x,y) cerr<< #x <<" = "<< x <<"  "<< #y <<" = "<< y <<endl
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,1):0;}
template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,1):0;}
template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}
template<typename T>inline T read(T&x){
    x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1;
    while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x;
}
const int N=5e5+7;
int n,m,s,cnt;
struct thxorz{
    int head[N*5],nxt[N*21],to[N*21],w[N*21],tot;
    inline void add(int x,int y,int z){to[++tot]=y,nxt[tot]=head[x],head[x]=tot,w[tot]=z;}
}G;
struct SGT{
    int id[N<<2];
    #define lc i<<1
    #define rc i<<1|1
    void build(int i,int L,int R,int dir){
        if(L==R){id[i]=L;return;}
        id[i]=++cnt;int mid=L+R>>1;//dbg2(i,cnt),dbg2(L,R);
        build(lc,L,mid,dir),build(rc,mid+1,R,dir);
        if(!dir)G.add(id[i],id[lc],0),G.add(id[i],id[rc],0);
        else G.add(id[lc],id[i],0),G.add(id[rc],id[i],0);
    }
    void update(int i,int L,int R,int ql,int qr,int dir){
        if(ql<=L&&qr>=R){dir?G.add(cnt,id[i],1):G.add(id[i],cnt,0);return;}
        int mid=L+R>>1;
        if(ql<=mid)update(lc,L,mid,ql,qr,dir);
        if(qr>mid)update(rc,mid+1,R,ql,qr,dir);
    }
}A,B;
priority_queue<pii,vector<pii>,greater<pii> > pq;
int dis[N*5];
#define y G.to[j]
inline void dij(){
    memset(dis,0x3f,sizeof dis);pq.push(make_pair(dis[s]=0,s));
    while(!pq.empty()){
        int d=pq.top().first,x=pq.top().second;pq.pop();
        if(dis[x]^d)continue;
        for(register int j=G.head[x];j;j=G.nxt[j])if(MIN(dis[y],d+G.w[j]))pq.push(make_pair(dis[y],y));
    }
}
#undef y
int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);
    cnt=read(n),read(m),read(s);
    A.build(1,1,n,0),B.build(1,1,n,1);
    for(register int i=1,l1,r1,l2,r2;i<=m;++i){
        read(l1),read(r1),read(l2),read(r2);
        ++cnt,B.update(1,1,n,l2,r2,0),A.update(1,1,n,l1,r1,1);
        ++cnt,B.update(1,1,n,l1,r1,0),A.update(1,1,n,l2,r2,1);
    }
    dij();
    for(register int i=1;i<=n;++i)printf("%d
",dis[i]);
    return 0;
}

不过，这题鉴于全是0/1边，所以直接一个0/1BFS就可以线性解决了。。并没有快多少可能是deque的锅。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define mst(x) memset(x,0,sizeof x)
#define dbg(x) cerr << #x << " = " << x <<endl
#define dbg2(x,y) cerr<< #x <<" = "<< x <<"  "<< #y <<" = "<< y <<endl
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,1):0;}
template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,1):0;}
template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}
template<typename T>inline T read(T&x){
    x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1;
    while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x;
}
const int N=5e5+7;
int n,m,s,cnt;
struct thxorz{
    int head[N*5],nxt[N*21],to[N*21],w[N*21],tot;
    inline void add(int x,int y,int z){to[++tot]=y,nxt[tot]=head[x],head[x]=tot,w[tot]=z;}
}G;
struct SGT{
    int id[N<<2];
    #define lc i<<1
    #define rc i<<1|1
    void build(int i,int L,int R,int dir){
        if(L==R){id[i]=L;return;}
        id[i]=++cnt;int mid=L+R>>1;//dbg2(i,cnt),dbg2(L,R);
        build(lc,L,mid,dir),build(rc,mid+1,R,dir);
        if(!dir)G.add(id[i],id[lc],0),G.add(id[i],id[rc],0);
        else G.add(id[lc],id[i],0),G.add(id[rc],id[i],0);
    }
    void update(int i,int L,int R,int ql,int qr,int dir){
        if(ql<=L&&qr>=R){dir?G.add(cnt,id[i],1):G.add(id[i],cnt,0);return;}
        int mid=L+R>>1;
        if(ql<=mid)update(lc,L,mid,ql,qr,dir);
        if(qr>mid)update(rc,mid+1,R,ql,qr,dir);
    }
}A,B;
deque<pii> q;
int dis[N*5];
#define y G.to[j]
inline void dij(){
    memset(dis,0x3f,sizeof dis);q.push_back(make_pair(dis[s]=0,s));
    while(!q.empty()){
        int d=q.front().first,x=q.front().second;q.pop_front();
        if(d^dis[x])continue;
        for(register int j=G.head[x];j;j=G.nxt[j])if(MIN(dis[y],d+G.w[j]))
            G.w[j]?q.push_back(make_pair(dis[y],y)):q.push_front(make_pair(dis[y],y));
    }
}
#undef y
int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);
    cnt=read(n),read(m),read(s);
    A.build(1,1,n,0),B.build(1,1,n,1);
    for(register int i=1,l1,r1,l2,r2;i<=m;++i){
        read(l1),read(r1),read(l2),read(r2);
        ++cnt,B.update(1,1,n,l2,r2,0),A.update(1,1,n,l1,r1,1);
        ++cnt,B.update(1,1,n,l1,r1,0),A.update(1,1,n,l2,r2,1);
    }
    dij();
    for(register int i=1;i<=n;++i)printf("%d
",dis[i]);
    return 0;
}

总结：区间建边，线段树。。