線段樹優化建圖

mb5ff40b968831d 2021-09-18 11:43:19 阅读数:577


前言

鳴謝 ckj 學長,yyds

引子

挺簡單但是很實用的一種建圖方法,可以將 \(O(n^2)\) 的建圖優化到 \(O(n~log n)\)

先看一道例題 ​ ​CF786B Legacy​

題目大意:有 \(n\) 個點、\(q\) 次操作。每一種操作為以下三種類型中的一種:

  • 操作一:連一條 \(u→v\) 的有向邊,權值為 \(w\)
  • 操作二:對於所有 \(i∈[l,r]\) 連一條 \(u→i\) 的有向邊,權值為 \(w\)。
  • 操作三:對於所有 \(i∈[l,r]\) 連一條 \(i→u\) 的有向邊,權值為 \(w\)。

求從點 \(s\) 到其他點的最短路。\(1≤n,q≤10^5,1≤w≤10^9\)

mind

首先想到的肯定是暴力建圖,每一次操作 \(O(n)\) 掃一邊,顯然會超時

因為是對一個區間進行操作,所以考慮用線段樹來搞點事情

建兩棵線段樹,一棵為"出樹"(所有邊指向兒子),一棵是 "入樹" (所有邊指向父親)

對向區間建邊的,可以在線段樹上找到這段區間,然後直接指向這段區間就好了

具體操作可以講的超級詳細

學的時候唯一難理解的是實際點的編號是如何和線段樹中編號怎麼避免沖突的?

其實每個點都對應著線段樹中的一個葉子節點,對於每個點的實際標號,可以理解為線段樹中是第幾個葉子,然後它肯定要對應線段樹的一個標號,而我們建圖是只利用線段樹的編號進行建圖,所以每一個點都要對應到線段樹上的點才能連邊(建圖),這樣就保證了只會用到線段樹的編號,避免了矛盾

code

/*
work by:Ariel_
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define int long long
#define lson rt << 1
#define rson rt << 1|1
using namespace std;
const int N = 3e6 + 5, K = 5e5 + 5;
int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
int n, m, s, opt, a[N];
struct edge{int v, nxt, w;}e[N];
int head[N], E;
void add_edge(int u, int v, int w) {
e[++E] = (edge) {v, head[u], w};
head[u] = E;
}
namespace Seg{
void build(int rt, int l, int r) {
if (l == r) {a[l] = rt; return;}
int mid = (l + r) >> 1;
add_edge(rt, rt << 1, 0), add_edge(rt, rt << 1 | 1, 0);
add_edge((rt << 1) + K, rt + K, 0), add_edge((rt << 1 | 1) + K, rt + K, 0);
build(lson, l, mid), build(rson, mid + 1, r);
}
void modify(int rt, int l, int r, int L, int R, int v, int w) {
if (L <= l && r <= R) {
if (opt == 2) add_edge(v + K, rt, w);
else add_edge(rt + K, v, w);
return;
}
int mid = (l + r) >> 1;
if (L <= mid) modify(lson, l, mid, L, R, v, w);
if (R > mid) modify(rson, mid + 1, r, L, R, v, w);
}
}
using namespace Seg;
priority_queue<pair<int, int> > q;
int dis[N], vis[N];
void dij(int s) {
memset(dis, 0x3f, sizeof dis), dis[s] = 0;
q.push(make_pair(0, s));
while(q.size()) {
int u = q.top().second; q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v;
if (e[i].w + dis[u] < dis[v]) {
dis[v] = e[i].w + dis[u];
q.push(make_pair(-dis[v], v));//默認從小到大排序,所以要取負號
}
}
}
}
signed main(){
n = read(), m = read(), s = read();
build(1, 1, n);
for (int i = 1; i <= n; i++) add_edge(a[i], a[i] + K, 0), add_edge(a[i] + K, a[i], 0);
for (int i = 1, x, y, z, l, r, w; i <= m; i++) {
opt = read();
if (opt == 1) {
x = read(), y = read(), z = read();//這裏的 x, y 對應線段樹的第幾個葉子節點,a[x] 存的是線段樹中第 x 葉子節點的標號
add_edge(a[x] + K, a[y], z);
}
else {
x = read(), l = read(), r = read(), w = read();
modify(1, 1, n, l, r, a[x], w);
}
}
dij(a[s] + K);
for (int i = 1; i <= n; i++)
printf("%lld%c",dis[a[i]]!=0x3f3f3f3f3f3f3f3fll?dis[a[i]]:-1,i==n?'\n':' ');
puts("");
return 0;
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.
  • 48.
  • 49.
  • 50.
  • 51.
  • 52.
  • 53.
  • 54.
  • 55.
  • 56.
  • 57.
  • 58.
  • 59.
  • 60.
  • 61.
  • 62.
  • 63.
  • 64.
  • 65.
  • 66.
  • 67.
  • 68.
  • 69.
  • 70.
  • 71.
  • 72.
  • 73.
  • 74.
  • 75.
  • 76.
  • 77.
  • 78.
  • 79.
  • 80.
  • 81.
  • 82.
  • 83.
  • 84.


寫在後面

關於優化建圖的方式還有分塊優化建圖,KD 樹優化建圖,主席樹連邊……

爭取退役前幹完 QWQ


版权声明:本文为[mb5ff40b968831d]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/09/20210918114319418x.html