Problem 遗产
题目大意
给出一个带权有向图，有三种操作：
1.u->v添加一条权值为w的边
2.区间[l,r]->v添加权值为w的边
3.v->区间[l,r]添加权值为w的边
求st点到每个点的最短路
Solution
首先我们思考到，若是每次对于l,r区间内的每一个点都执行一次加边操作，不仅耗时还耗空间。
那么我们要想到一个办法去优化它。一看到lr区间，我们就会想到线段树对吧。
没错啦这题就是用线段树去优化它。
首先我们建一棵线段树，然后很容易想到，我们只需要把这一棵线段树当做图中的一部分去跑dijkstra，也可以跑出正确答案。
当然这棵树上的每一条边边权都为0。
看到2.3操作，我们需要建两颗线段树，其中一颗线段树是区间到点，另一个是点到区间。
区间到点的线段树是反着连有向边的，这个简单思考一下便可得出。
建树的时候我们需要对于每一个叶子节点连向对应的单点。
这样一来，因为每个区间最多只会有$\log n$个点，我们只需要最多连$\log n$条边就可以完成一次加边操作。
最后跑dijkstra的时候一定要加堆优化，否则会很惨的。。因为边数特别大。。。
当然本题解写的非常之简略，可以去bilibili[嘿嘿嘿]搜索“codeforces div ABC”(好像是这样)就可以搜索到某大神的直播讲题。
好的接下来是扯淡时间，首先我先在自己学校oj上交了一发，然后a掉了。于是我就很高兴地开始写本篇题解。写着写着突然想去cf上面交一发。。然后直接第七个点就爆炸了。对拍以后发现是自己的dijkstra出了问题。
那么现在问题来了，为什么我们的oj上可以ac呢？
调了数据发现我们oj上的数据只有五个点&&前四个点n<5。。。。
于是就继续改，对拍了一个中午都没错。。结果发现自己oj上拿下来的标程是错的。。
然而这个题目我卡了好久好久好久好久啊。。都快调疯了。
最后发现是dijkstra写错了。。。我都想扇死自己了。
最后A掉了以后，搞了一发数据，扔到了oj上，卡掉了80%的Ac代码。
还有一个非常需要注意到的地方是，总的边数经过计算可得知为$6n+q\log n$条边，也就是≥2500000。
点数也要开到5n级别，也就是≥500000。
还有，dijkstra的distance数组一定要开long long不然会炸裂
加边时间复杂度：$O(q\log n)$
最短路时间复杂度$O(n\log(q\log n))$
Data Maker
此题的数据生成器：（建议调数据大小的时候要在全程序范围内修改，否则只修改define部分会跑出来非法的数据，可不能怪我哟嘿嘿嘿）
#include <ctime>
#include <cstdio>
#include <iostream>
#include <cstdlib>
#define maxN 100000
#define maxQ 100000
#define maxW 100000000
#define starT (rand()%100000+1)
using namespace std;
int main(){
srand((unsigned)time(NULL));
freopen("cf787d7.in","w",stdout);
int n=maxN,q=maxQ,s=starT;
printf("%d %d %d\n",n,q,s);
for(int i=;i<=q;i++){
int num=rand()%+;
if(num==)printf("1 %d %d %d\n",rand()%maxN+,rand()%maxN+,rand()%maxW+);
else if(num<){
int l=rand()%+;
printf("2 %d %d %d %d\n",rand()%maxN+,l,l++rand()%()+,rand()%maxW+);
}else{
int l=rand()%+;
printf("3 %d %d %d %d\n",rand()%maxN+,l,l++rand()%()+,rand()%maxW+);
}
}
}
AC Code
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
int n,eq,s,u,v,l,r,Tsk,nodetot,now,tot=;
priority_queue< pair<long long,int> > q;
struct node{
int to,next,w;
}e[];
bool vis[];
int h[],lch[],w;
long long dist[];
void add(int u,int v,int w){
e[++tot].to=v;e[tot].next=h[u];h[u]=tot;e[tot].w=w;
}
int read(){
int x=,f=;
char c=getchar();
for (;!isdigit(c);c=getchar())if(c=='-')f=-;
for (;isdigit(c);c=getchar())x=x*+c-'';
return x*f;
}
void addTree(int v,int l,int r,long long w,int nl,int nr,int now){
if(nl>=l&&nr<=r)add(v,now,w);
else{
int mid=(nl+nr)>>;
if(r<=mid)addTree(v,l,r,w,nl,mid,lch[now-n]);
else if(l>mid)addTree(v,l,r,w,mid+,nr,lch[now-n]+);
else{
addTree(v,l,mid,w,nl,mid,lch[now-n]);
addTree(v,mid+,r,w,mid+,nr,lch[now-n]+);
}
}
}
void Treeadd(int v,int l,int r,long long w,int nl,int nr,int now){
if(nl>=l&&nr<=r)add(now,v,w);
else{
int mid=(nl+nr)>>;
if(r<=mid)Treeadd(v,l,r,w,nl,mid,lch[now-n]);
else if(l>mid)Treeadd(v,l,r,w,mid+,nr,lch[now-n]+);
else{
Treeadd(v,l,mid,w,nl,mid,lch[now-n]);
Treeadd(v,mid+,r,w,mid+,nr,lch[now-n]+);
}
}
}
void buildTreest(int now,int l,int r){
if(l==r){
add(now,l,);
return;
};
int mid=(l+r)>>;
add(now,++nodetot,);
lch[now-n]=nodetot;
add(now,++nodetot,);
buildTreest(lch[now-n],l,mid);
buildTreest(lch[now-n]+,mid+,r);
}
void buildTreeet(int now,int l,int r){
if(l==r){
add(l,now,);
return;
};
int mid=(l+r)>>;
add(++nodetot,now,);
lch[now-n]=nodetot;
add(++nodetot,now,);
buildTreeet(lch[now-n],l,mid);
buildTreeet(lch[now-n]+,mid+,r);
}
void Dijkstra(int st){
dist[st]=;
now=st;
q.push(make_pair(,st));
while(!q.empty()){
vis[now]=;
pair<long long,int> x=q.top();
q.pop();
now=x.second;
for(int i=h[now];~i;i=e[i].next){
if(dist[e[i].to]>dist[now]+e[i].w){
dist[e[i].to]=dist[now]+e[i].w;
q.push(make_pair(-dist[e[i].to],e[i].to));
}
}
}
}
int main(){
memset(h,-,sizeof(h));
memset(dist,0x7f,sizeof(dist));
n=read();
eq=read();
s=read();
nodetot=n+;
buildTreest(n+,,n);
buildTreeet(++nodetot,,n);
for(int i=;i<=eq;i++){
Tsk=read();
if(Tsk==){
v=read();
u=read();
w=read();
add(v,u,w);
}else if(Tsk==){
v=read();
l=read();
r=read();
w=read();
addTree(v,l,r,w,,n,n+);
}else{
v=read();
l=read();
r=read();
w=read();
Treeadd(v,l,r,w,,n,n*);
}
}
Dijkstra(s);
for(int i=;i<=n-;i++)printf("%lld ",(dist[i]==0x7f7f7f7f7f7f7f7f)?-:dist[i]);
printf("%lld\n",(dist[n]==0x7f7f7f7f7f7f7f7f)?-:dist[n]);
}