A：区间 [l1,r1] -> [l2,r2] 连有权边跑 dij 优化建图能不能优化？
Q：能。直接优化建图+普通堆是O(nlog^2n)的，实际上可以隐式建图，线段树+vector即可。可以做到 O(nlogn)
代码超级小清新！！
点击查看代码
array<int,3> v[MAX];
vector<int> e[MAX<<2];
bool vis[MAX];
int mn[MAX<<2],sz[MAX<<2],tag[MAX<<2];
void pushdown(int rt){
if(sz[ls(rt)]){
mn[ls(rt)] = min(mn[ls(rt)],tag[rt]);
tag[ls(rt)] = min(tag[ls(rt)],tag[rt]);
}
if(sz[rs(rt)]){
mn[rs(rt)] = min(mn[rs(rt)],tag[rt]);
tag[rs(rt)] = min(tag[rs(rt)],tag[rt]);
}
tag[rt] = inf;
return ;
}
void pushup(int rt){
sz[rt] = sz[ls(rt)]+sz[rs(rt)];
mn[rt] = min(mn[ls(rt)],mn[rs(rt)]);
return ;
}
void build(int lp,int rp,int rt){
if(lp==1)mn[rt]=0;
else mn[rt] = inf;
tag[rt] = inf;
sz[rt] = rp-lp+1;
if(lp>=rp)return ;
int mid = (lp+rp)>>1;
build(lp,mid,ls(rt));
build(mid+1,rp,rs(rt));
return ;
}
void add(int lp,int rp,int l,int r,int idx,int rt){
if(l<=lp&&rp<=r){
e[rt].pb(idx);
return ;
}
int mid = (lp+rp)>>1;
if(l<=mid)add(lp,mid,l,r,idx,ls(rt));
if(r>mid)add(mid+1,rp,l,r,idx,rs(rt));
return ;
}
void chkmin(int lp,int rp,int l,int r,int val,int rt){
if(!sz[rt])return ;
if(l<=lp&&rp<=r){
mn[rt] = min(mn[rt],val);
tag[rt] = min(tag[rt],val);
return ;
}
int mid = (lp+rp)>>1;
pushdown(rt);
if(l<=mid)chkmin(lp,mid,l,r,val,ls(rt));
if(r>mid)chkmin(mid+1,rp,l,r,val,rs(rt));
pushup(rt);
return ;
}
void upd(int lp,int rp,int rt){
for(auto idx:e[rt]){
if(!vis[idx]){
vis[idx] = 1;
chkmin(1,n,v[idx][0],v[idx][1],v[idx][2]+val);
}
}
e[rt].clear();
if(lp>=rp){
sz[rt] = 0;
mn[rt] = inf;
return ;
}
pushdown(rt);
int mid = (lp+rp)>>1;
if(mn[ls(rt)]==mn[rt])upd(lp,mid,val,ls(rt));
else upd(mid+1,rp,val,rs(rt));
pushup(rt);
return ;
}