cf 787D 线段树优化建图 + 单源最短路

模型：
1e5次操作，有三种操作，操作1，两个单点加边，操作2，1个单点对l~r区间加边w，操作3，l～r区间对单点加边。
思路：
由于是区间操作，线段树建图
建立对顶线段树a，b ，注意图中的有向边边权都是0
操作1 b的单点连向a的单点
操作2 b的单点连向a中区间包含在l～r之间的点
操作3 b中区间包含在l～r之间的点连向a中的单点

#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=9*N+(100010)*20;
#define int long long 
const int INF=0x3f3f3f3f3f3f3f3f;
struct node{
    int l,r;
    int id;
}tr1[N<<2],tr2[N<<2];
int h[N*8],e[M],ne[M],w[M];
int id,idx;
int sum;
int n,q,s;
int d[N*8];
bool st[N*8];
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void build1(int u,int l,int r)
{
    tr1[u].id=++id;
    tr1[u].l=l,tr1[u].r=r;
    if(l==r)    return ;
    int mid=l+r>>1;
    build1(u<<1,l,mid);
    build1(u<<1|1,mid+1,r);
    add(tr1[u].id,tr1[u<<1].id,0),add(tr1[u].id,tr1[u<<1|1].id,0);
}
void build2(int u,int l,int r)
{
    tr2[u].id=++id;
    tr2[u].l=l,tr2[u].r=r;
    if(l==r)    return ;
    int mid=l+r>>1;
    build2(u<<1,l,mid);
    build2(u<<1|1,mid+1,r);    
    add(tr2[u<<1].id,tr2[u].id,0),add(tr2[u<<1|1].id,tr2[u].id,0);
}
int qra(int u,int pos)
{
    if(tr1[u].l==tr1[u].r)
        return tr1[u].id;
    int mid = tr1[u].l + tr1[u].r>>1;
    if(pos<=mid)
        return qra(u<<1,pos);
    else
        return qra(u<<1|1,pos);
}
int qrb(int u, int pos)
{
    if(tr2[u].l==tr2[u].r)
        return tr2[u].id;
    int mid=tr2[u].l+tr2[u].r>>1;
    if(pos<=mid)
        return qrb(u<<1,pos);
    else
        return qrb(u<<1|1,pos);
}
void updatea(int u,int pos,int l,int r,int w)
{
    if(tr1[u].l>=l && tr1[u].r<=r)
    {
        add(pos,tr1[u].id,w);
        return ;    
    }
    int mid=tr1[u].l+tr1[u].r>>1;
    if(l<=mid)
        updatea(u<<1,pos,l,r,w);
    if(r>mid)
        updatea(u<<1|1,pos,l,r,w);
}
void updateb(int u,int pos,int l,int r,int w)
{
    if(tr2[u].l>=l && tr2[u].r<=r)
    {
        add(tr2[u].id,pos,w);
        return ;
    }
    int mid=tr2[u].l+tr2[u].r>>1;
    if(l<=mid)
        updateb(u<<1,pos,l,r,w);
    if(r>mid)
        updateb(u<<1|1,pos,l,r,w);
}
struct nd{
    int x;
    int y;
    bool operator<(const nd&W)const
    {
        return x>W.x;
    }
};
void dijkstra()
{
     s = qra(1,s);
    memset(d,0x3f,sizeof d);
    d[s]=0;
    priority_queue<nd> q;
    q.push({0ll,s});
    while(q.size())
    {
        auto t=q.top();
        q.pop();
        int u=t.y;
        if(st[u])    continue;
        st[u]=true;
        for(int i=h[u];~i;i=ne[i])
        {
            int j=e[i];
            if(d[j]>d[u]+w[i])
            {
                d[j]=d[u]+w[i];
                q.push({d[j],j});
            }
        }
    }

}
signed main()
{
    cin>>n>>q>>s;
    memset(h,-1,sizeof h);
    build1(1,1,n);
    build2(1,1,n);
    for(int i=1;i<=n;i++)
    {
        //cout<<qra(1,i)<<" "<<qrb(1,i)<<endl;
        add(qra(1,i),qrb(1,i),0);
    }
    int pos1,pos2;
    int a,b,w,l,r,v;
    while(q--)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            cin>>a>>b>>w;
            pos1=qrb(1,a);
            pos2=qra(1,b);
            add(pos1,pos2,w);
        }
        else if(op==2)
        {
             cin>>v>>l>>r>>w;
            pos1=qrb(1,v);
            updatea(1,pos1,l,r,w);
        }
        else
        {
            cin>>v>>l>>r>>w;
            pos1=qra(1,v);
            updateb(1,pos1,l,r,w);
        }
    }
    dijkstra();
    int res=0;
    for(int i=1;i<=n;i++)
    {
        res=d[qra(1,i)];
        //cout<<res<<endl;
        if(res==INF)
            cout<<-1<<" ";
        else
            cout<<res<<" ";
    }
    cout<<endl;
    return 0;
}