P5618 SDOI2015 道路修建题解

题目分析

虽然数据范围只有 \(n\le60000\)，但是完全可以直接用线段树做。

首先考虑那种状态的图在左边和右边加入节点和边之后可以连通。容易发现，这种图有这两个性质：

• 至少有一条路径，经过最左端和最右端中的点。
• 所有点至少和最左端和最右端的点连通。

于是可以划分成以下几种状态：

1. 最左端两个点不连通，最右端两个点不连通，只有一条经过最左端和最右端中的点的路径；
2. 最左端两个点连通，最右端两个点不连通；
3. 最左端两个点不连通，最右端两个点连通；
4. 最左端两个点连通，最右端两个点连通；
5. 最左端两个点不连通，最右端两个点不连通，有两条经过最左端和最右端中的点的路径。

如图：

然后分类讨论每两种状态的连接方法和结果状态，如图所示的几种情况：

剩余情况见代码 pushup 函数。

用线段树维护，记录以下东西：

• \(a,b\)：区间左端点和又端点。
• \(v1,v2,v3,v4,v5\)：区间中每种状态最小费用。

对于竖边修改，修改包含需要修改的点的区间；对于横边修改，只需修改列数较小的点即可。

查询输出对应区间的 \(v4\) 的。

这里有个坑点：输入修改操作时可能把列数大的点放在前面，这时要把较小的点设为后输入的点。

示例代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 60005, INF = 2e9;

int n, m;
int x[N], y[N], z[N];
struct node{
	int a, b;
	LL v1, v2, v3, v4, v5;
}t[N * 4];

void pushup(node &u, node ls, node rs)
{
	int p = x[ls.b], q = y[ls.b], c = p + q, d = min(p, q);
	u.v1 = u.v2 = u.v3 = u.v4 = u.v5 = INF;
	u.v1 = min(u.v1, ls.v1 + rs.v2 + c);
	u.v3 = min(u.v3, ls.v1 + rs.v4 + c);
	u.v1 = min(u.v1, ls.v1 + rs.v5 + c);
	u.v2 = min(u.v2, ls.v2 + rs.v2 + c);
	u.v4 = min(u.v4, ls.v2 + rs.v4 + c);
	u.v2 = min(u.v2, ls.v2 + rs.v5 + c);
	u.v1 = min(u.v1, ls.v3 + rs.v1 + c);
	u.v1 = min(u.v1, ls.v3 + rs.v2 + d);
	u.v3 = min(u.v3, ls.v3 + rs.v3 + c);
	u.v3 = min(u.v3, ls.v3 + rs.v4 + d);
	u.v3 = min(u.v3, ls.v3 + rs.v5 + c);
	u.v1 = min(u.v1, ls.v3 + rs.v5 + d);
	u.v2 = min(u.v2, ls.v4 + rs.v1 + c);
	u.v2 = min(u.v2, ls.v4 + rs.v2 + d);
	u.v4 = min(u.v4, ls.v4 + rs.v3 + c);
	u.v4 = min(u.v4, ls.v4 + rs.v4 + d);
	u.v4 = min(u.v4, ls.v4 + rs.v5 + c);
	u.v2 = min(u.v2, ls.v4 + rs.v5 + d);
	u.v1 = min(u.v1, ls.v5 + rs.v1 + c);
	u.v2 = min(u.v2, ls.v5 + rs.v2 + c);
	u.v1 = min(u.v1, ls.v5 + rs.v2 + d);
	u.v3 = min(u.v3, ls.v5 + rs.v3 + c);
	u.v4 = min(u.v4, ls.v5 + rs.v4 + c);
	u.v3 = min(u.v3, ls.v5 + rs.v4 + d);
	u.v5 = min(u.v5, ls.v5 + rs.v5 + c);
	u.v1 = min(u.v1, ls.v5 + rs.v5 + d);
	u.a = ls.a, u.b = rs.b;
}

void build(int u, int a, int b)
{
	t[u].a = a, t[u].b = b;
	if(a == b)
	{
		t[u].v1 = t[u].v2 = t[u].v3 = INF;
		t[u].v5 = 0;
		t[u].v4 = z[a];
		return ;
	}
	int mid = a + b >> 1, ls = u << 1, rs = ls | 1;
	build(ls, a, mid), build(rs, mid + 1, b);
	pushup(t[u], t[ls], t[rs]);
}

void modify(int u, int d)
{
	if(t[u].a == t[u].b)
	{
		t[u].v1 = t[u].v2 = t[u].v3 = INF;
		t[u].v5 = 0;
		t[u].v4 = z[t[u].a];
		return ;
	}
	int ls = u << 1, rs = ls | 1;
	if(t[ls].b >= d) modify(ls, d);
	else modify(rs, d);
	pushup(t[u], t[ls], t[rs]);
}

node query(int u, int x, int y)
{
	if(x <= t[u].a && t[u].b <= y) return t[u];
	int ls = u << 1, rs = ls | 1;
	if(t[ls].b >= x && t[rs].a <= y)
	{
		node res;
		pushup(res, query(ls, x, y), query(rs, x, y));
		return res;
	}
	else if(t[ls].b >= x) return query(ls, x, y);
	else return query(rs, x, y);
}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i < n; i ++ ) scanf("%d", &x[i]);
	for(int i = 1; i < n; i ++ ) scanf("%d", &y[i]);
	for(int i = 1; i <= n; i ++ ) scanf("%d", &z[i]);
	
	build(1, 1, n);
	while(m -- )
	{
		char op[2];
		scanf("%s", op);
		if(*op == 'Q')
		{
			int l, r;
			scanf("%d%d", &l, &r);
			printf("%lld\n", query(1, l, r).v4);
		}
		else
		{
			int ax, bx, ay, by, w;
			scanf("%d%d%d%d%d", &ay, &ax, &by, &bx, &w);
			if(ax == bx)
			{
				z[ax] = w;
				modify(1, ax);
			}
			else
			{
				if(ax > bx) ax = bx;
				if(ay == 1) x[ax] = w;
				else y[ax] = w;
				modify(1, ax);
			}
		}
	}
	return 0;
}