「CF787D」遺產(Legacy)-線段樹-優化Dijkstra

給出一個帶權有向圖，有三種操作：

1.u->v添加一條權值為w的邊

2.區間[l,r]->v添加權值為w的邊

3.v->區間[l,r]添加權值為w的邊

求st點到每個點的最短路

首先我們思考到，若是每次對於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+qlog n$條邊，也就是≥2500000。

點數也要開到5n級別，也就是≥500000。

還有，dijkstra的distance數組一定要開long long不然會炸裂

加邊時間複雜度：$O(qlog n)$

最短路時間複雜度$O(nlog(qlog n))$

此題的數據生成器：（建議調數據大小的時候要在全程序範圍內修改，否則只修改define部分會跑出來非法的數據，可不能怪我喲嘿嘿嘿）

1 #include
2 #include
3 #include
4 #include
5 #define maxN 100000
6 #define maxQ 100000
7 #define maxW 100000000
8 #define starT (rand%100000+1)
9 using namespace std;
10 int main{
11 srand((unsigned)time(NULL));
12 freopen("cf787d7.in","w",stdout);
13 int n=maxN,q=maxQ,s=starT;
14 printf("%d %d %d
",n,q,s);
15 for(int i=1;i<=q;i++){ 16 int num=rand%11+1; 17 if(num==1)printf("1 %d %d %d ",rand%maxN+1,rand%maxN+1,rand%maxW+900000000); 18 else if(num<7){ 19 int l=rand%10000+1; 20 printf("2 %d %d %d %d ",rand%maxN+1,l,l+30000+rand%(60000)+1,rand%maxW+900000000); 21 }else{ 22 int l=rand%10000+1; 23 printf("3 %d %d %d %d ",rand%maxN+1,l,l+30000+rand%(60000)+1,rand%maxW+900000000); 24 } 25 } 26 }

AC Code

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 using namespace std;
8 int n,eq,s,u,v,l,r,Tsk,nodetot,now,tot=0;
9 priority_queue< pair > q;
10 struct node{
11 int to,next,w;
12 }e[7000070];
13 bool vis[700050];
14 int h[700050],lch[700040],w;
15 long long dist[700050];
16 void add(int u,int v,int w){
17 e[++tot].to=v;e[tot].next=h[u];h[u]=tot;e[tot].w=w;
18 }
19 int read{
20 int x=0,f=1;
21 char c=getchar;
22 for (;!isdigit(c);c=getchar)if(c=="-")f=-1;
23 for (;isdigit(c);c=getchar)x=x*10+c-"0";
24 return x*f;
25 }
26 void addTree(int v,int l,int r,long long w,int nl,int nr,int now){
27 if(nl>=l&&nr<=r)add(v,now,w); 28 else{ 29 int mid=(nl+nr)>>1;
30 if(r<=mid)addTree(v,l,r,w,nl,mid,lch[now-n]); 31 else if(l>mid)addTree(v,l,r,w,mid+1,nr,lch[now-n]+1);
32 else{
33 addTree(v,l,mid,w,nl,mid,lch[now-n]);
34 addTree(v,mid+1,r,w,mid+1,nr,lch[now-n]+1);
35 }
36 }
37 }
38 void Treeadd(int v,int l,int r,long long w,int nl,int nr,int now){
39 if(nl>=l&&nr<=r)add(now,v,w); 40 else{ 41 int mid=(nl+nr)>>1;
42 if(r<=mid)Treeadd(v,l,r,w,nl,mid,lch[now-n]); 43 else if(l>mid)Treeadd(v,l,r,w,mid+1,nr,lch[now-n]+1);
44 else{
45 Treeadd(v,l,mid,w,nl,mid,lch[now-n]);
46 Treeadd(v,mid+1,r,w,mid+1,nr,lch[now-n]+1);
47 }
48 }
49 }
50 void buildTreest(int now,int l,int r){
51 if(l==r){
52 add(now,l,0);
53 return;
54 };
55 int mid=(l+r)>>1;
56 add(now,++nodetot,0);
57 lch[now-n]=nodetot;
58 add(now,++nodetot,0);
59 buildTreest(lch[now-n],l,mid);
60 buildTreest(lch[now-n]+1,mid+1,r);
61 }
62 void buildTreeet(int now,int l,int r){
63 if(l==r){
64 add(l,now,0);
65 return;
66 };
67 int mid=(l+r)>>1;
68 add(++nodetot,now,0);
69 lch[now-n]=nodetot;
70 add(++nodetot,now,0);
71 buildTreeet(lch[now-n],l,mid);
72 buildTreeet(lch[now-n]+1,mid+1,r);
73 }
74 void Dijkstra(int st){
75 dist[st]=0;
76 now=st;
77 q.push(make_pair(0,st));
78 while(!q.empty){
79 vis[now]=1;
80 pair x=q.top;
81 q.pop;
82 now=x.second;
83 for(int i=h[now];~i;i=e[i].next){
84 if(dist[e[i].to]>dist[now]+e[i].w){
85 dist[e[i].to]=dist[now]+e[i].w;
86 q.push(make_pair(-dist[e[i].to],e[i].to));
87 }
88 }
89 }
90 }
91 int main{
92 memset(h,-1,sizeof(h));
93 memset(dist,0x7f,sizeof(dist));
94 n=read;
95 eq=read;
96 s=read;
97 nodetot=n+1;
98 buildTreest(n+1,1,n);
99 buildTreeet(++nodetot,1,n);
100 for(int i=1;i<=eq;i++){ 101 Tsk=read; 102 if(Tsk==1){ 103 v=read; 104 u=read; 105 w=read; 106 add(v,u,w); 107 }else if(Tsk==2){ 108 v=read; 109 l=read; 110 r=read; 111 w=read; 112 addTree(v,l,r,w,1,n,n+1); 113 }else{ 114 v=read; 115 l=read; 116 r=read; 117 w=read; 118 Treeadd(v,l,r,w,1,n,n*3); 119 } 120 } 121 Dijkstra(s); 122 for(int i=1;i<=n-1;i++)printf("%lld ",(dist[i]==0x7f7f7f7f7f7f7f7f)?-1:dist[i]); 123 printf("%lld ",(dist[n]==0x7f7f7f7f7f7f7f7f)?-1:dist[n]); 124 }

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！