线段树优化建边（CF786B Legacy题解）
suxxsfe
2020-02-21 20:11:22
[模板题CF786B Legacy](https://www.luogu.com.cn/problem/CF786B)
先说算法
如果需要有n个点需要建图
给m个需要建边的信息，从单点（或区间内所有点）向一区间所有点连边
如果暴力建图复杂度$mn^2$
以单点连向区间为例，在n个点上建一颗线段树，叶子节点即为这n个点，每个节点向它的左右儿子连一个权值为0的边，这样我们只要向一个节点连边，也就相当于向它所在的区间每个点都连边了（因为连到这个节点，就能顺着线段树中0边权的路一路走到叶子节点，也就是真正存在的节点）
这样可以用类似与线段树区间查找的方法，以$logn$的复杂度向$[l,r]$内所有点连边
如果是区间连向区间（$[l,r]$连向$[l',r']$），可以建两颗线段树，一棵in（由外面往这颗树连边）树，一棵out（由这棵树向外连边）树，和一个虚拟节点
在out树中从$[l,r]$向虚拟节点连边，再由虚拟节点向in树中的$[l',r']$连边
注意这里out树是有区间往外连，所以线段树中的边是由儿子连向父亲，因为如果编号为pos的节点要向外连一条边，它要先顺着线段树中的边走到某一个父亲，再由此去其他节点
再看这道题就简单了
也是要建一颗in树一颗out树
第一种方案直接连边
第二种方案由节点v向in树中$[l,r]$连边
第三种由out树中$[l,r]$向v节点连边
最后跑个最短路就行了
具体实现见代码
```cpp
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstring>
#define R register
#define EN std::puts("")
#define LL long long
inline int read(){
int x=0,y=1;
char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
int n,m,s,nn;
int fir[500006],nex[4000005],to[4000006],len[4000006],tot;
struct tr{
tr *ls,*rs;
int id;
}dizhi[400006],*rootin=&dizhi[0],*rootout=&dizhi[1];
int dizhitot=1;
LL dis[500006];
int in[500006];
int dui[500006],size;
inline void push(int x){
dui[size++]=x;
R int i=size-1,fa;
while(i){
fa=i>>1;
if(dis[dui[fa]]<=dis[dui[i]]) return;
std::swap(dui[fa],dui[i]);i=fa;
}
}
inline int pop(){
int ret=dui[0];dui[0]=dui[--size];
R int i=0,ls,rs;
while((i<<1)<size){
ls=i<<1;rs=ls|1;
if(rs<size&&dis[dui[rs]]<dis[dui[ls]]) ls=rs;
if(dis[dui[ls]]>=dis[dui[i]]) break;
std::swap(dui[ls],dui[i]);i=ls;
}
return ret;
}
inline void dij(){
std::memset(dis,0x3f,sizeof dis);
in[s]=1;push(s);dis[s]=0;
while(size){
R int u=pop();in[u]=0;
for(R int i=fir[u];i;i=nex[i]){
R int v=to[i];
if(dis[v]>dis[u]+len[i]){
dis[v]=dis[u]+len[i];
if(!in[v]) push(v),in[v]=1;
}
}
}
}
inline void add(int u,int v,int w){
to[++tot]=v;len[tot]=w;
nex[tot]=fir[u];fir[u]=tot;
}
void build(tr *treein,tr *treeout,int l,int r){
if(l==r){treein->id=treeout->id=l;return;}
int mid=(l+r)>>1;
treein->ls=&dizhi[++dizhitot];treein->rs=&dizhi[++dizhitot];
treeout->ls=&dizhi[++dizhitot];treeout->rs=&dizhi[++dizhitot];
build(treein->ls,treeout->ls,l,mid);build(treein->rs,treeout->rs,mid+1,r);
treein->id=++nn;treeout->id=++nn;
add(treein->id,treein->ls->id,0);add(treein->id,treein->rs->id,0);
add(treeout->ls->id,treeout->id,0);add(treeout->rs->id,treeout->id,0);
}
void addtreein(tr *tree,int l,int r,int ql,int qr,int u,int w){
if(ql<=l&&r<=qr){add(u,tree->id,w);return;}
int mid=(l+r)>>1;
if(ql<=mid) addtreein(tree->ls,l,mid,ql,qr,u,w);
if(qr>mid) addtreein(tree->rs,mid+1,r,ql,qr,u,w);
}
void addtreeout(tr *tree,int l,int r,int ql,int qr,int v,int w){
if(ql<=l&&r<=qr){add(tree->id,v,w);return;}
int mid=(l+r)>>1;
if(ql<=mid) addtreeout(tree->ls,l,mid,ql,qr,v,w);
if(qr>mid) addtreeout(tree->rs,mid+1,r,ql,qr,v,w);
}
int main(){
nn=n=read();m=read();s=read();
build(rootin,rootout,1,n);
while(m--){
int op=read();
if(op==1){
int u=read(),v=read(),w=read();
add(u,v,w);
}
else if(op==2){
int u=read(),l=read(),r=read(),w=read();
addtreein(rootin,1,n,l,r,u,w);
}
else{
int v=read(),l=read(),r=read(),w=read();
addtreeout(rootout,1,n,l,r,v,w);
}
}
dij();
for(R int i=1;i<=n;i++)
std::printf("%lld ",dis[i]==0x3f3f3f3f3f3f3f3f?-1:dis[i]);
return 0;
}
```
### 最后丢下几个例题
[洛谷P3588 [POI2015]PUS](https://www.luogu.com.cn/problem/P3588)
[题解](https://www.luogu.com.cn/blog/suxxsfe/solution-p3588)
[bzoj5017[Snoi2017]炸弹](https://www.lydsy.com/JudgeOnline/problem.php?id=5017) /[洛谷P5025 [SNOI2017]炸弹](https://www.luogu.com.cn/problem/P5025)
[题解](https://www.luogu.com.cn/blog/suxxsfe/ti-xie-bzoj5017snoi2017-zha-tan)，~~当时交了一页最后发现是没开long long~~
[bzoj3073[Pa2011]Journeys](https://www.lydsy.com/JudgeOnline/problem.php?id=3073)，算是一个模板题了，就是那种边从区间连向区间的情况，而且这是01边权，用双端队列bfs就行，看网上好多人都写的dij
但需要权限，所以可以去[这上面](https://darkbzoj.tk/problem/3073)看看
~~题解没写~~
[bzoj2143飞飞侠](https://www.lydsy.com/JudgeOnline/problem.php?id=2143)，一开始写了个那种三维的dp，但不知道是常数问题还是写炸了已知TLE，之后改的线段树建边
~~题解依旧没写~~
[CF1045A Last chance](http://codeforces.com/contest/1045/problem/A)，这个还需要网络流，不会，以后再写吧。。