题解 CF786B 【Legacy】

· · 题解

题意分析

这一题最主要是有三种操作：1.进行单点与单点连有向边 2.进行单点与区间连有向边 3.进行区间与单点连有向边。然后求最短路。

这一道题，最大的难点不在最短路（直接套Dij模板），而在于如何连边。如果按照题意模拟，一个点到区间中的一个点进行连接，其复杂度在最坏情况下会达到O(n*n)（即每一个点向整个区间连边），任何一个有常识的人都能看出这样一定会TLE的。

对于我们来说，最大的难点就是要解决单点与区间之间的操作。一看到区间，我们首先想到的就是前缀和、差分、ST表、树状数组、线段树。其实，这一题本质上就是一道特殊的线段树题。

那么怎么把一个线段树放到图里面呢？这里我们发现，如果只建立一个线段树是很难实现的，那么我们一不做二不休，就建立两个线段树。

int n,q,s,cnt,treeOut[MAXN<<2],treeIn[MAXN<<2];

我们用treeOut专门处理由线段树向外连边，其效果如图所示：

有图可见，我们在线段树内建立了多条有向虚边。且treeIn和treeOut的线段树虚边的方向是相反的，如图则是treeIn：

那么为什么要这样建立虚边，这里就用一张图来演示一下： 由图可知，错误的连边会导致访问的区间出错。比如在这张错误的图中，一个只能访问[mid+1,right]的连边却访问到了[left,right]。

代码

static vector<pair<int,int>> edge[MAXN*10];

我们使用vector建图，相比于链表来说会方便一些（2s,STL不怂）。

inline void build(int k,int l,int r){
    if(l==r){
        treeOut[k]=l;
        treeIn[k]=l;
        return;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    treeOut[k]=++cnt;
    treeIn[k]=++cnt;
    edge[treeOut[k<<1]].push_back make(treeOut[k],0);
    edge[treeOut[k<<1|1]].push_back make(treeOut[k],0);
    edge[treeIn[k]].push_back make(treeIn[k<<1],0);
    edge[treeIn[k]].push_back make(treeIn[k<<1|1],0);
}
inline void updateIn(int k,int l,int r,int L,int R,int from,int cost){
    if(L<=l&&r<=R){
        edge[from].push_back(make(treeIn[k],cost));
        return ;
    }
    int mid=(l+r)>>1;
    if(L<=mid){
        updateIn(k<<1,l,mid,L,R,from,cost);
    }
    if(mid<R){
        updateIn(k<<1|1,mid+1,r,L,R,from,cost);
    }
}
inline void updateOut(int k,int l,int r,int L,int R,int from,int cost){
    if(L<=l&&r<=R){
        edge[treeOut[k]].push_back(make(from,cost));
        return ;
    }
    int mid=(l+r)>>1;
    if(L<=mid){
        updateOut(k<<1,l,mid,L,R,from,cost);
    }
    if(mid<R){
        updateOut(k<<1|1,mid+1,r,L,R,from,cost);
    }
}

常规的建树操作，最大的区别是要在建树的时候还要进行建图操作。树的每一个节点储存着该区间在图中的编号。需要注意的是，当该区间就是一个点时,树中储存的就是改点的便后，即：

if(l==r){
        treeOut[k]=l;
        treeIn[k]=l;
        return;
}

在这道题中，update的作用不在于修改树中的值，而是在于建图，这是他与一般线段树的区别。 以下是全部代码：

#include<bits/stdc++.h>
#define ini(x,y) memset(x,y,sizeof(x))
#define all(x) x.begin(),x.end()
#define F(x,y,z) for(int x=y;x<=z;++x)
#define D(x,y,z) for(int x=y;x>=z;--x)
#define cint const int&
using namespace std;
/*请以C++11提交,Develop By ZhangXinjie（江南柚子）*/
const int MAXN=static_cast<int>(1e5)+100;
const long long INF=0x3f3f3f3f3f3f3f3f;
const int oo=0x3f3f3f3f;
#define int long long
inline int read(){
    int x = 0, y = 1, c = getchar();
    while (c>'9' || c<'0') { if (c == '-')y = -1; c = getchar(); }
    while (c >= '0'&&c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    return x * y;
}
#define make(x,y) (make_pair(x,y))
#define to first
#define v second
static vector<pair<int,int>> edge[MAXN*10];
static int n,q,s,cnt,treeOut[MAXN<<2],treeIn[MAXN<<2];
inline void build(int k,int l,int r){
    if(l==r){
        treeOut[k]=l;
        treeIn[k]=l;
        return;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    treeOut[k]=++cnt;
    treeIn[k]=++cnt;
    edge[treeOut[k<<1]].push_back make(treeOut[k],0);
    edge[treeOut[k<<1|1]].push_back make(treeOut[k],0);
    edge[treeIn[k]].push_back make(treeIn[k<<1],0);
    edge[treeIn[k]].push_back make(treeIn[k<<1|1],0);
}
inline void updateIn(int k,int l,int r,int L,int R,int from,int cost){
    if(L<=l&&r<=R){
        edge[from].push_back(make(treeIn[k],cost));
        return ;
    }
    int mid=(l+r)>>1;
    if(L<=mid){
        updateIn(k<<1,l,mid,L,R,from,cost);
    }
    if(mid<R){
        updateIn(k<<1|1,mid+1,r,L,R,from,cost);
    }
}
inline void updateOut(int k,int l,int r,int L,int R,int from,int cost){
    if(L<=l&&r<=R){
        edge[treeOut[k]].push_back(make(from,cost));
        return ;
    }
    int mid=(l+r)>>1;
    if(L<=mid){
        updateOut(k<<1,l,mid,L,R,from,cost);
    }
    if(mid<R){
        updateOut(k<<1|1,mid+1,r,L,R,from,cost);
    }
}
struct heapnode{
    int pos,dis;
    bool operator<(heapnode right)const{
        return dis>right.dis;
    }
};

static int dis[MAXN*10];
static priority_queue<heapnode>heap;
inline void dij(){
    ini(dis,0x3f);
    dis[s]=0;
    heapnode tmp;
    tmp.dis=0;
    tmp.pos=s;
    heap.push(tmp);
    while(!heap.empty()){
        heapnode now=heap.top();
        heap.pop();
        if(dis[now.pos]!=now.dis){
            continue;
        }
        for(auto &i:edge[now.pos]){
            if(i.to==0){
                continue;
            }
            if(i.v+now.dis<dis[i.to]){
                dis[i.to]=i.v+now.dis;
                tmp.pos=i.to;
                tmp.dis=dis[i.to];
                heap.push(tmp);
            }
        }
    }
}
signed main(){
    n=read();
    q=read();
    s=read();
    cnt=n;
    build(1,1,n);
    F(i,1,q){
        int com=read();
        if(com==1){
            int from=read(),to=read(),v=read();
            edge[from].push_back(make(to,v));
        }else{
            if(com==2){
                int from=read(),l=read(),r=read(),v=read();
                updateIn(1,1,n,l,r,from,v);
            }else{
                int from=read(),l=read(),r=read(),v=read();
                updateOut(1,1,n,l,r,from,v);
            }
        }
    }
    dij();
    F(i,1,n){
        printf("%lld ",(dis[i]==INF)?-1:dis[i]);
    }
    return 0;
}

至于为什么使用dij算法而不用SPFA，因为

1<=w<=10^9

以及NOI2018D1T1的血的教训。

还有，记得使用long long