CF786B Legacy

博主： tony102
发布时间：2020 年 12 月 02 日
1580 次浏览
暂无评论
2079字数
分类：题解

[Link](https://www.luogu.com.cn/problem/CF786B)

## Sol

这是一道线段树优化连边板子题

要用这个的题通常是这样的, 一个点往一个区间内所有点连边,或者一个区间都往一个点连边. 如果你直接暴力连的话时间很差劲,你就需要线段树优化连边.

思路大概是这样的,运用线段树的思想. 线段树的每一个叶子节点对应原图的节点, 非叶节点就对应的是一段区间的点. 这样一来连边就只需要连接线段树上的点.

比如说一个题往一个区间内所有点连边,就是从线段树的叶节点往一个代表整个区间的点连边.这样相当于是从线段树深度比较深的底部往浅的地方连. 一个区间都往一个点连就是往下连. 每次都按照递归在线段树上找一下对应区间的节点,然后连就可以了.

实现的话都可以, 这道题这两种连边都有. 就直接开两个动态开点线段树, 然后共用叶子节点

## Code

~~不懂的问题看了代码就懂了~~

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SIZE = 4e5 + 5;
const int inf = 1e18;

int n, q, s, root1, root2, nodeCnt, num;
int head[SIZE], dis[SIZE], vis[SIZE], lson[SIZE], rson[SIZE];

struct edge {
	int to, v, nxt;
} edge[SIZE * 10];

namespace ae86 {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (!isdigit(c))b ^= c == '-', c = fetch();
		while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
}
using ae86::read;

inline void addEdge(int u, int v, int d) {
	edge[++ num].to = v, edge[num].v = d, edge[num].nxt = head[u];
	head[u] = num;
}

inline int buildDown(int l, int r) {
	if (l == r) return l;
	int mid = (l + r) >> 1, p = ++ nodeCnt;
	lson[p] = buildDown(l, mid); rson[p] = buildDown(mid + 1, r);
	addEdge(p, lson[p], 0); addEdge(p, rson[p], 0);
	return p;
}

inline int buildUp(int l, int r) {
	if (l == r) return l;
	int mid = (l + r) >> 1, p = ++ nodeCnt;
	lson[p] = buildUp(l, mid); rson[p] = buildUp(mid + 1, r);
	addEdge(lson[p], p, 0); addEdge(rson[p], p, 0);
	return p;
}

inline void link(int from, int to, int val, int l, int r, int L, int R, int typ) {
	if (L <= l && r <= R) {
		if (typ == 1) addEdge(from, to, val); // up -> down
		else addEdge(to, from, val); // down -> up
		return;
	}
	int mid = (l + r) >> 1;
	if (L <= mid) link(lson[from], to, val, l, mid, L, R, typ);
	if (R > mid) link(rson[from], to, val, mid + 1, r, L, R, typ);
}

inline void dijkstra() {
	std::priority_queue < pair < int, int > > q;
	for (int i = 1; i <= nodeCnt; ++ i) dis[i] = inf;
	memset(vis, 0, sizeof(vis));
	q.push(make_pair(0, s)); dis[s] = 0;
	while (!q.empty()) {
		int u = q.top().second, v;
		q.pop();
		if (vis[u]) continue; vis[u] = 1;
		for (int i = head[u]; i; i = edge[i].nxt) {
			v = edge[i].to;
			if (dis[v] > dis[u] + edge[i].v) {
				dis[v] = dis[u] + edge[i].v;
				q.push(make_pair(-dis[v], v));
			}
		}
	}
}

signed main() {
	// freopen("code.in", "r", stdin);
	// freopen("code.out", "w", stdout);
	nodeCnt = n = read(), q = read(), s = read(); root1 = nodeCnt + 1;
	buildDown(1, n); root2 = nodeCnt + 1;
	buildUp(1, n);
	int opt, v, u, l, r, w;
	while (q --) {
		opt = read();
		if (opt == 1) {
			u = read(), v = read(), w = read();
			addEdge(u, v, w);
		}
		else {
			u = read(), l = read(), r = read(), w = read();
			link(opt ^ 3 ? root1 : root2, u, w, 1, n, l, r, opt - 2);
		}
	}
	dijkstra();
	for (int i = 1; i <= n; ++ i) printf("%lld ", dis[i] == inf ? -1 : dis[i]);
	return 0;
}
```

最后修改：2021 年 09 月 04 日