线段树优化建图

· · 算法·理论

线段树优化建图

例题：CF786B

题目意思差不多就是对于区间进行连边，边有边权，然后求起点到其它点的最短路。

主要优化思路就是线段树。我们考虑建两棵线段树，每个节点维护的区间就存着对应区间的连边信息。一颗内向一颗外向，两棵树本质相同，都是维护节点的信息，所以说两棵树每对对应的叶子节点都要互相连一条边权位 0 的边，如图：

这幅图中的所有边边权均为 0。显然（）。然后考虑如何进行连边操作。容易发现连边其实都应该是右边的线段树连向左边的线段树（内向树连向外向树），这样才能保证从点出发能经过所连的边。假如说从外向树连向内向树，那么可能出现无法到达的情况。感觉还是比较显然的（）

具体的连边：

其中点连点怎么连都行（）

tips：处理节点的时候不要把 leaf_v 写成 v 了（

连完边之后就正常跑 Dij 即可~

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define ls (root << 1)
#define rs (root << 1 | 1)
#define mid ((l + r) >> 1)
const int MAX = 1e5 + 5;
const int mod = 998244353;
const int INF = 0x7fffffff;
const int p = 4e5+1;
inline int read(){
    int x=0,y=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar())if(c=='-')y=-1;
    for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
    return x*y;
}
int n,Q,s,dis[MAX<<3],leaf[MAX];
struct Day_Tao {int v,w;};
vector<Day_Tao>e[MAX<<3];
inline void build(int l,int r,int root)
{
    if(l==r) return leaf[l]=root,void();
    e[root].push_back({ls,0}),e[root].push_back({rs,0});
    e[ls+p].push_back({root+p,0}),e[rs+p].push_back({root+p,0});
    build(l,mid,ls),build(mid+1,r,rs); return ;
}
void update(int l,int r,int root,int ql,int qr,int v,int w,int op)
{
    if(r<ql||l>qr) return ;
    if(ql<=l&&r<=qr)
    {
        if(op&1) e[root+p].push_back({v,w});
        else e[v+p].push_back({root,w}); return ;
    }
    update(l,mid,ls,ql,qr,v,w,op),update(mid+1,r,rs,ql,qr,v,w,op); return ;
}
priority_queue<pii,vector<pii>,greater<pii>>q;
bool vis[MAX<<3];
signed main()
{
//  freopen(".in","r",stdin),freopen(".out","w",stdout);
    n=read(),Q=read(),s=read();
    build(1,n,1);
    while(Q--)
    {
        int op=read(),v=read(),l=read(),r=read(),w;
        if(op==1) e[leaf[v]].push_back({leaf[l],r});
        else w=read(),update(1,n,1,l,r,leaf[v],w,op);
    }
    for(int i=1;i<=n;i++) e[leaf[i]].push_back({leaf[i]+p,0}),e[leaf[i]+p].push_back({leaf[i],0});
    memset(dis,0x3f,sizeof(dis)),dis[leaf[s]+p]=0,q.push({0,leaf[s]+p});
    while(!q.empty())
    {
        int u=q.top().second;q.pop();
        if(!vis[u])
        {
            vis[u]=1;
            for(Day_Tao i:e[u])
            {
                int v=i.v,w=i.w;
                if(dis[v]>dis[u]+w) dis[v]=dis[u]+w,q.push({dis[v],v});
            }
        }
    }
    for(int i=1;i<=n;i++) if(dis[leaf[i]]==0x3f3f3f3f3f3f3f3f) printf("-1 ");else printf("%lld ",dis[leaf[i]]);
    return 0;
}