先從一道例題開始：CodeForces - 786B Legacy

題意：

　　有n（≤10⁵）個點，q（≤10⁵）個操作，每個操作為以下三種操作之一：

　　操作一：u到[l,r]之間的點建一條邊權為w的有向邊；

　　操作二：[l,r]的點到u之間建一條邊權為w的有向邊；

　　操作三：u到v建一條邊權為w的有向邊；

　　求點到其他點的最短路，無法到達的點輸出-1。

分析：

　　此題的難點在于建邊。對于操作一和操作二，直接建邊O(n²)，肯定會TLE。

　　考慮到需要對區間進行操作，我們可以利用利用線段樹的結構來優化建邊。具體做法如下：

　　一、建立兩棵線段樹（全是虛點），一棵由父親向兒子連邊，一棵由兒子向父親連邊，邊權都為0，兩棵樹的葉節點都編號為1-n。

　　二、對于操作一和操作二，利用線段樹拆分區間，之后從u向拆分后的區間對應的虛點連邊，邊權為w。

　　如此一來，建邊的效率應該可以優化到O（log（n））。

　　放上核心代碼:

void build(int p,int l,int r){t[p].l=o[p].l=l;t[p].r=o[p].r=r;if(l==r){t[p].pos=o[p].pos=l;return;}int mid=(l+r)>>1;t[p].pos=++cnt;o[p].pos=++cnt;build(lc,l,mid);build(rc,mid+1,r);add(t[p].pos,t[lc].pos,0);add(t[p].pos,t[rc].pos,0);add(o[lc].pos,o[p].pos,0);add(o[rc].pos,o[p].pos,0); } void admi(int p,int l,int r,int u,LL dis,int opt){//此題數據比較大記得開long long（代碼中已將其定義為LL）if(l<=t[p].l&&t[p].r<=r){if(opt==2) add(u,t[p].pos,dis);else if(opt==3) add(o[p].pos,u,dis);return;}int mid=(t[p].l+t[p].r)>>1;if(l<=mid) admi(lc,l,r,u,dis,opt);if(r> mid) admi(rc,l,r,u,dis,opt); }

?

例題：WOJ4578 Journeys

題意：

　　有n(n≤5*10⁵)個點，m（n≤10⁵）個操作，每個操作將[l1,r1]之間的點與[l2,r2]之間的點一一建邊（無向邊）。求起點到所有點所經過的最少邊數（保證起點可以到打所有點）。

分析：

　　跟上一道題差不多。考慮用線段樹優化建圖，但是發現區間和區間之間不好連邊。怎么辦？

　　添加虛點。

　　我們先把無向邊拆成兩條有向邊，對于每條有向邊，我們都設置一個虛點，于是問題就轉化成了由區間向虛點連邊，再由虛點向區間連邊（這不就是上一題嗎？）。為了方便計算，我們把每條邊去設為1，這樣在最后輸出答案時對每個點到起點的最短路除以2即可得到正確的答案。

　　放上代碼：

#include<bits/stdc++.h> using namespace std; #define N 8000010 #define INF 0x3f3f3f3f #define lc (p<<1) #define rc (p<<1|1) int n,m,st,cnt,num,d[N],f[N],vis[N]; struct node{int u,v,w,nxt; }e[N]; struct tree{int l,r,pos; }t[N],o[N]; void add(int u,int v,int w){e[++num]=(node){u,v,w,f[u]};f[u]=num;} void build(int p,int l,int r){t[p].l=o[p].l=l;t[p].r=o[p].r=r;if(l==r){t[p].pos=o[p].pos=l;return;}int mid=(l+r)>>1;t[p].pos=++cnt;o[p].pos=++cnt;build(lc,l,mid);build(rc,mid+1,r);add(t[p].pos,t[lc].pos,0);add(t[p].pos,t[rc].pos,0);add(o[lc].pos,o[p].pos,0);add(o[rc].pos,o[p].pos,0); } void admi(int p,int l,int r,int u,int opt){if(l<=t[p].l&&t[p].r<=r){if(opt==0) add(u,t[p].pos,1);else if(opt==1) add(o[p].pos,u,1);return;}int mid=(t[p].l+t[p].r)>>1;if(l<=mid) admi(lc,l,r,u,opt);if(r> mid) admi(rc,l,r,u,opt); } typedef pair<int,int> T; void dijkstra(int s){memset(vis,0,sizeof(vis));memset(d,0x3f,sizeof(d));priority_queue< T,vector<T>, greater<T> >q;d[s]=0;q.push(make_pair(d[s],s));while(!q.empty()){pair<int,int> t=q.top();q.pop();int dd=t.first,u=t.second;if(vis[u]) continue;vis[u]=1;for(int i=f[u];i;i=e[i].nxt){int v=e[i].v,w=e[i].w;if(d[v]>dd+w){d[v]=dd+w;q.push(make_pair(d[v],v));}}} } int main(){int x,y,s,t;scanf("%d%d%d",&n,&m,&st);cnt=n;build(1,1,n);for(int i=1;i<=m;i++){scanf("%d%d%d%d",&x,&y,&s,&t);cnt++;admi(1,x,y,cnt,0);admi(1,s,t,cnt,1);cnt++;admi(1,x,y,cnt,1);admi(1,s,t,cnt,0);}dijkstra(st);for(int i=1;i<=n;i++) printf("%d\n",d[i]/2);return 0; }

轉載于:https://www.cnblogs.com/doyo2019/p/11073448.html

總結

以上是生活随笔為你收集整理的线段树优化建图的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。