Codeforces Round #406 (Div. 2) D. Legacy 线段树建图求最短路

有 n 个点，初时没有边，m 次操作，操作分为三种

1、加一条从 u 到 v 的权值为 val 的边

2、加一条从 u 到 [ql,qr] 区间所有点的权值为 val 的边

3、加一条从 [ql,qr] 到 u 区间所有点的权值为 val 的边

最后求一个单源最短路。

1、显然暴力建边会超时，那么我们考虑分块，将它分为  个 块，每块长度为 ，然后发现时间复杂度为 ，由于常数太大，应该会超时。

2、分块超时一定是分块不够优雅，考虑线段树的 build 过程，将整个区间分为了 nlogn 个区间，并且区间修改的复杂度是 logn ，看起来有点香。

3、考虑将所有线段树的区间看成一个点，那么当我们进行 2 操作的时候，一个点走向一个区间的点，就意味着这个点向这个区间连边.

4、考虑 一个点走向一个区间 和 一个区间走向一个点，第一种，一个点能走到这个区间，说明他能走到所有这个区间的子区间，第二种，一个区间的点都能走到 一个点，说明所有能走到覆盖这个区间的点都能走到 一个点，这两种状态是不同的，所以考虑建两颗线段树，一颗自上到下建单向边，一颗自下到上建单向边，第一棵树维护操作2，第二颗树维护操作3就可以了。

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)>>1;
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXN_DOT = 3e5 + 5;
struct edge
{
	int to;
	ll w;
	int nex;
}e[MAXN * 68];
int head[MAXN_DOT], tot;
void init()
{
	memset(head, -1, sizeof(head));
	tot = 1;
}
void add(int u, int v, ll w)
{
	e[tot] = edge{ v,w,head[u] };
	head[u] = tot++;
}
struct segment
{
	int l;
	int r;
	int flag;
}que_up[MAXN * 4], que_down[MAXN * 4];
int tot_dot;
int n, q, s;
int ql, qr;
ll val;
//从上到下建边
void build_up(int left = 1, int right = n, int k = 1, int fa = 0)
{
	que_up[k].l = left;
	que_up[k].r = right;
	if (left == right)
	{
		que_up[k].flag = left;
		add(fa, left, 0);
		return;
	}
	if (fa)
		add(fa, tot_dot, 0);
	int u = tot_dot;
	que_up[k].flag = tot_dot++;

	imid;
	build_up(lson, u);
	build_up(rson, u);
}
void update_up(int left = 1, int right = n, int k = 1, int u = 0)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		add(u, que_up[k].flag, val);
		return;
	}
	imid;
	update_up(lson, u);
	update_up(rson, u);
}
//从下到上建边
void build_down(int left = 1, int right = n, int k = 1, int fa = 0)
{
	que_down[k].l = left;
	que_down[k].r = right;
	if (left == right)
	{
		que_down[k].flag = left;
		add(left, fa, 0);
		return;
	}
	if (fa)
		add(tot_dot, fa, 0);
	int u = tot_dot;
	que_down[k].flag = tot_dot++;

	imid;
	build_down(lson, u);
	build_down(rson, u);
}
void update_down(int left = 1, int right = n, int k = 1, int u = 0)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		add(que_down[k].flag, u, val);
		return;
	}
	imid;
	update_down(lson, u);
	update_down(rson, u);
}
#define Pair pair<ll,int>
ll dis[MAXN_DOT];
bool vis[MAXN_DOT];
void dij(int s, int n)
{
	for (int i = 0; i < MAXN_DOT; i++)
		dis[i] = 1e18 + 7;
	priority_queue<Pair, vector<Pair>, greater<Pair> > q;
	dis[s] = 0;
	q.push(Pair{ 0,s });
	while (!q.empty())
	{
		int u = q.top().second;
		q.pop();
		if (vis[u])
			continue;
		vis[u] = true;
		for (int i = head[u]; i + 1; i = e[i].nex)
		{
			int to = e[i].to;
			if (dis[u] + e[i].w < dis[to])
			{
				dis[to] = dis[u] + e[i].w;
				q.push(Pair{ dis[to],to });
			}
		}
	}
	for (int i = 1; i <= n; i++)
		pr("%lld%c", dis[i] == 1e18 + 7 ? -1 : dis[i], i == n ? '\n' : ' ');
}
int main()
{
	init();
	sc("%d%d%d", &n, &q, &s);
	tot_dot = n + 1;
	build_up();
	build_down();
	while (q--)
	{
		int op;
		sc("%d", &op);
		if (op == 1)
		{
			sc("%d%d%lld", &ql, &qr, &val);
			add(ql, qr, val);
		}
		else
		{
			int u;
			sc("%d%d%d%lld", &u, &ql, &qr, &val);
			if (op == 2)
				update_up(1, n, 1, u);
			else
				update_down(1, n, 1, u);
		}
	}
	dij(s, n);
}