应该算是比较丝薄无味的一个题目, 按照题目诞生的时间推断, 出题人应该是借鉴了SHOI2008的堵塞的交通,并且难度还降低了。

简单的来说, 是线段树维护连通性的裸题。

题目链接

题目大意

维护两行点的区间最小生成树? 支持修改边权的操作。

解题报告

因为只有两行点么, 所以可以把同一列的两个点当做线段树上的一个节点。

维护四个信息, 对于区间\([l,r]\), 分别表示:

  1. as[l,r] : \([l,r]\)之间的\(2(r-l+1)\)个的的最小生成树;
  2. ls[l,r] : \([l,r]\)之间, 第\(l\)行的两个点不联通, 形成两个联通块的最小代价;
  3. rs[l,r] : \([l,r]\)之间, 第\(r\)行的两个点不连通, 形成两个联通块的最小代价;
  4. ts[l,r] : \([l,r]\)之间, 第\(l\)行的两个点不连通, 第\(r\)行的两个点不连通, 形成三个联通块的最小代价。

通过手动的讨论, 可以得到合并两个区间的转移:

1
2
3
4
5
6
7
8
9
10
11
12
cmin(x.as,l.as+r.as+a);
cmin(x.as,l.rs+r.as+a+b);
cmin(x.as,l.as+r.ls+a+b);
cmin(x.ls,l.ls+r.as+a);
cmin(x.ls,l.ls+r.ls+a+b);
cmin(x.ls,l.ts+r.as+a+b);
cmin(x.rs,l.as+r.rs+a);
cmin(x.rs,l.rs+r.rs+a+b);
cmin(x.rs,l.as+r.ts+a+b);
cmin(x.ts,l.ls+r.rs+a);
cmin(x.ts,l.ls+r.ts+a+b);
cmin(x.ts,l.ts+r.rs+a+b);

奇怪的是, 这个题目就这样完结了。。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=int(a),nn=int(b);i<=nn;++i)
#define vep(i,a,b) for(int i=int(a),nn=int(b);i>=nn;--i)
#define xep(i,b) for(int i=0,nn=int(b);i<nn;++i)
const int N=60010;
const int inf=500000000;
int n,m,lo[N],lw[N],c[N];
struct four {
int as, ls, rs, ts;
four() {as=ls=ts=ts=inf;}
four(int as,int ls,int rs,int ts)
: as(as),ls(ls),rs(rs),ts(ts){}
} s[N<<2];
inline void in(int &x) {
char ch=getchar(); int f=1;
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (x=0;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-48;
x*=f;
}
template<typename T> inline void cmin(T &x,T a){x=a<x?a:x;}
four merge(four l, four r,int a,int b) {
if (a>b) swap(a,b) ;
four x(inf,inf,inf,inf);
cmin(x.as,l.as+r.as+a);
cmin(x.as,l.rs+r.as+a+b);
cmin(x.as,l.as+r.ls+a+b);
cmin(x.ls,l.ls+r.as+a);
cmin(x.ls,l.ls+r.ls+a+b);
cmin(x.ls,l.ts+r.as+a+b);
cmin(x.rs,l.as+r.rs+a);
cmin(x.rs,l.rs+r.rs+a+b);
cmin(x.rs,l.as+r.ts+a+b);
cmin(x.ts,l.ls+r.rs+a);
cmin(x.ts,l.ls+r.ts+a+b);
cmin(x.ts,l.ts+r.rs+a+b);
return x;
}
void build(int x,int l,int r) {
if (l==r) { s[x]=four(c[l],0,0,inf);}
else { int mid=(l+r)>>1;
build(x<<1, l, mid);
build(x<<1|1,mid+1,r);
s[x]=merge(s[x<<1],s[x<<1|1],lo[mid],lw[mid]);
}
}
void change(int x,int l,int r,int p) {
if (l==r) { s[x]=four(c[l],0,0,inf);}
else { int mid=(l+r)>>1;
if (p<=mid) change(x<<1,l,mid,p);
else change(x<<1|1,mid+1,r,p);
s[x]=merge(s[x<<1],s[x<<1|1],lo[mid],lw[mid]);
}
}
void modify(int x,int l,int r,int p) {
int mid=(l+r)>>1; if (mid==p) {
s[x]=merge(s[x<<1],s[x<<1|1],lo[mid],lw[mid]);
return ;
} else {
if (l==r) return ;
if (p<=mid) modify(x<<1,l,mid,p);
else modify(x<<1|1,mid+1,r,p);
s[x]=merge(s[x<<1],s[x<<1|1],lo[mid],lw[mid]);
}
}
four query(int x,int l,int r,int _l,int _r) {
if (_l<=l&&r<=_r) return s[x];
int mid=(l+r)>>1;
if (_r<=mid) return query(x<<1,l,mid,_l,_r);
if (_l>mid) return query(x<<1|1,mid+1,r,_l,_r);
return merge(query(x<<1,l,mid,_l,_r),
query(x<<1|1,mid+1,r,_l,_r),lo[mid],lw[mid]);
}
int main() {
in(n),in(m);
rep(i,1,n-1) in(lo[i]); rep(i,1,n-1) in(lw[i]);
rep(i,1,n) in(c[i]); build(1,1,n);
char tp[10]; int l,r,_l,_r,w; four an;
xep(I, m) { scanf("%s", tp);
if (tp[0]=='C') {
in(l),in(r),in(_l),in(_r),in(w);
if (r==_r) c[r]=w, change(1,1,n,r);
else { if (r>_r) swap(r,_r);
if (l==1) lo[r]=w; else lw[r]=w;
modify(1,1,n,r);
}
} else {
in(l),in(r), an=query(1,1,n,l,r);
printf("%d\n", an.as);
}
}
return 0;
}

留言