SDOI2015 道路修建（线段树）

发表于 |
字数统计: 1,807字 | 阅读时长 ≈ 9min

[SDOI2015]道路修建

问题描述

某国有2N个城市，这2N个城市构成了一个2行N列的方格网。现在该国政府有一个旅游发展计划，这个计划需要选定L、R两列(L<=R)，修建若干条专用道路，使得这两列之间（包括这两列）的所有2(R-L+1)个城市中每个城市可以只通过专用道路就可以到达这2(R-L+1)个城市中的任何一个城市。这种专用道路只能在同一行相邻两列的城市或者同一列的两个城市之间修建，且修建需要花费一定的费用。由于该国政府决定尽量缩减开支，因此政府决定，选定L、R后，只修建2(R-L+1)-1条专用道路，使得这些专用道路构成一个树结构。现在你需要帮助该国政府写一个程序，完成这个任务。具体地，该任务包含M个操作，每个操作的格式如下：

1.C x0 y0 x1 y1 w：由于重新对第x0行第y0列的城市和第x1行第y1列的城市之间的情况进行了考察，它们之间修建一条专用道路的花费变成了w；

2.Q L R：若政府选定的两列分别为L、R，询问政府的最小开支。

输入格式

第一行，两个整数N、M。

第二行，N-1个整数，其中第i个整数表示初始时第1行第i列的城市和第1行第i+1列的城市之间修建一条专用道路的费用。

第三行，N-1个整数，其中第i个整数表示初始时第2行第i列的城市和第2行第i+1列的城市之间修建一条专用道路的费用。

第四行，N个整数，其中第i个整数表示初始时第1行第i列的城市和第2行第i列的城市之间修建一条专用道路的费用。

接下来的M行，每行一个操作。

输出格式

对于每个询问操作，输出一行，表示你计算出的政府的最小开支。

样例输入

3 3

1 2

2 1

3 1 2

Q 1 3

C 1 2 2 2 3

Q 2 3

样例输出

7

5

提示

对于40%的数据，1<=N, M<=600；

对于全部的数据，1<=N, M<=60000，任何时刻任何一条专用道路的修建费用不超过$10^4$

观察可知，对于一个联通块，只需要维护它的四个角的联通情况就行了。因此对于一个联通块，最多存在$10$种可能联通情况，我们考虑用线段树维护区间联通信息，即每一种联通情况的最小费用，然后合并的时候讨论一下就行了。

然后观察转移发现实际上这$10$种情况本质不同的只有$5$种，并且合并时只需要考虑连$1$条边还是$2$条边，因此最多有$50$种转移，实际上没有这么多。然后询问就只需要将线段树上对应区间拿来合并就行了。

代码：

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 66666
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline int _R(int &x)
{
	char t=GC;
	while(t<48||t>57)t=GC;
	for(x=0;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
}
const int inf=1e9;
int n,m,UR[N],DR[N],D[N];
struct nodd
{
	int v[6];
	void Init()
	{
		for(int i=0;i<6;i++)v[i]=inf;
	}
};
struct node
{
	node *ls,*rs;
	nodd v;
}Seg[N<<2],*rt,*tl,*null;
void Init()
{
	rt=tl=null=&Seg[0];
	null->ls=null->rs=null;
	null->v.Init();
}
void Update(nodd &p,nodd &l,nodd &r,int a,int b)
{
	int c=min(a,b),d=a+b;p.Init();
	p.v[1]=min(p.v[1],l.v[1]+r.v[1]+c);
	p.v[1]=min(p.v[1],l.v[1]+r.v[2]+d);
	p.v[3]=min(p.v[3],l.v[1]+r.v[3]+c);
	p.v[3]=min(p.v[3],l.v[1]+r.v[4]+c);
	p.v[1]=min(p.v[1],l.v[1]+r.v[4]+d);
	p.v[3]=min(p.v[3],l.v[1]+r.v[5]+d);
	
	p.v[2]=min(p.v[2],l.v[2]+r.v[1]+c);
	p.v[2]=min(p.v[2],l.v[2]+r.v[2]+d);
	p.v[5]=min(p.v[5],l.v[2]+r.v[3]+c);
	p.v[5]=min(p.v[5],l.v[2]+r.v[4]+c);
	p.v[2]=min(p.v[2],l.v[2]+r.v[4]+d);
	p.v[5]=min(p.v[5],l.v[2]+r.v[5]+d);
	
	p.v[1]=min(p.v[1],l.v[3]+r.v[1]+d);
	p.v[3]=min(p.v[3],l.v[3]+r.v[3]+d);
	p.v[3]=min(p.v[3],l.v[3]+r.v[4]+d);
	
	p.v[2]=min(p.v[2],l.v[4]+r.v[1]+c);
	p.v[1]=min(p.v[1],l.v[4]+r.v[1]+d);
	p.v[2]=min(p.v[2],l.v[4]+r.v[2]+d);
	p.v[5]=min(p.v[5],l.v[4]+r.v[3]+c);
	p.v[3]=min(p.v[3],l.v[4]+r.v[3]+d);
	p.v[5]=min(p.v[5],l.v[4]+r.v[4]+c);
	p.v[4]=min(p.v[4],l.v[4]+r.v[4]+d);
	p.v[5]=min(p.v[5],l.v[4]+r.v[5]+d);
	
	p.v[2]=min(p.v[2],l.v[5]+r.v[1]+d);
	p.v[5]=min(p.v[5],l.v[5]+r.v[3]+d);
	p.v[5]=min(p.v[5],l.v[5]+r.v[4]+d);
}
void BT(node *&p,int l,int r)
{
	p=++tl;p->ls=p->rs=null;
	if(l==r)
	{
		p->v.v[1]=D[l];
		p->v.v[2]=p->v.v[3]=inf;
		p->v.v[4]=0;
		p->v.v[5]=inf;
		return;
	}
	int mid=l+r>>1;
	BT(p->ls,l,mid);
	BT(p->rs,mid+1,r);
	Update(p->v,p->ls->v,p->rs->v,UR[mid],DR[mid]);
}
void MD(node *p,int l,int r,int k)
{
	if(l==r)
	{
		p->v.v[1]=D[l];
		p->v.v[2]=p->v.v[3]=inf;
		p->v.v[4]=0;
		p->v.v[5]=inf;
		return;
	}
	int mid=l+r>>1;
	if(k<=mid)MD(p->ls,l,mid,k);
	else MD(p->rs,mid+1,r,k);
	Update(p->v,p->ls->v,p->rs->v,UR[mid],DR[mid]);
}
nodd Gans(node *p,int l,int r,int x,int y)
{
	if(x<=l&&y>=r)return p->v;
	int mid=l+r>>1;nodd a,b,t;
	a.Init();b.Init();t.Init();
	if(x>mid)return Gans(p->rs,mid+1,r,x,y);
	if(y<=mid)return Gans(p->ls,l,mid,x,y);
	a=Gans(p->ls,l,mid,x,y);
	b=Gans(p->rs,mid+1,r,x,y);
	Update(t,a,b,UR[mid],DR[mid]);
	return t;
}
int main()
{
	int i,j,k,x1,y1,x2,y2;
	_R(n);_R(m);char s;
	for(i=1;i<n;i++)_R(UR[i]);
	for(i=1;i<n;i++)_R(DR[i]);
	for(i=1;i<=n;i++)_R(D[i]);
	Init();BT(rt,1,n);
	for(i=1;i<=m;i++)
	{
		s=GC;while(s!='Q'&&s!='C')s=GC;
		if(s=='Q')
		{
			_R(x1);_R(x2);
			printf("%d\n",Gans(rt,1,n,x1,x2).v[1]);
		}
		else
		{
			_R(x1);_R(y1);_R(x2);_R(y2);_R(k);
			if(y1>y2)swap(y1,y2);
			if(x1==x2)x1==1?UR[y1]=k:DR[y1]=k;
			else D[y1]=k;
			MD(rt,1,n,y1);
		}
	}
}