[SDOI2015]道路修建
__Aaaaaaaa
·
·
题解
题面大意：给出两排点，给出同一列的两个点之间的边权和同一行相邻的点之间的边权，存在在线操作修改和查询，修改是某条边的边权，查询是一个区间内的最小生成树的边权总和。
Solution：
考虑用线段树维护每个区间的情况。
下面考虑转移：合并 $L$ 和 $R$ 两个节点，设 $L$ 表示区间内最右的纵边为 $y0$，$R$ 表示区间内最左的纵边为 $y1$，它们两个相邻区间中间的两条横边为 $x0$ 和 $x1$。
第一种情况是连接一条横边，即对于所有的 $(i,j,c1,c2\in [0,1])$ 都要执行以下转移。
```
U.dp[i][j]=min(U.dp[i][j],L.dp[i][c1]+R.[c2][j]+min(x0,x1));
```
第二种情况是 $y0$ 或 $y1$ 是保证连接的情况下，拆除其中一条，两条横边都连。
即对于所有的 $(i,j,c2\in [0,1])$ 都要执行以下转移。
```
U.dp[i][j]=min(U.dp[i][j],L.dp[i][1]+R.dp[c2][j]-y0+x0+x1);
```
对于所有的 $(i,j,c1\in [0,1])$ 都要执行以下转移。
```
U.dp[i][j]=min(U.dp[i][j],L.dp[i][c1]+R.dp[1][j]-y1+x0+x1);
```
还有就是要考虑 $L$ 或 $R$ 是叶子节点（最左等于最右）。
这样一来 ```pushup``` 函数就写好了 ~~，剩下的就是敲模板~~。
### Don't talk much:
```
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=6e4+10,INF=1e9;
struct tree{
int l,r;
int dp[2][2];
void init_INF(){
memset(dp,0x3f,sizeof dp);
}
}tr[N<<2];
int col[N],row1[N],row2[N];//对应位置的横边、纵边
void pushup(tree &U,tree &L,tree &R){
U.l=L.l,U.r=R.r;
int x0=row1[L.r],x1=row2[L.r];
int y0=col[L.r],y1=col[R.l];
bool leafL=L.l==L.r,leafR=R.l==R.r;
U.init_INF();
if(leafL&&leafR){//特判:左右都是叶子节点
U.dp[0][1]=x0+x1+y1;
U.dp[1][0]=x0+x1+y0;
U.dp[1][1]=y0+y1+min(x0,x1);
return;
}
else if(leafL){//特判:左儿子是叶子节点
U.dp[0][0]=x0+x1+min(R.dp[0][0],R.dp[1][0]);
U.dp[0][1]=x0+x1+min(R.dp[0][1],R.dp[1][1]);
U.dp[1][0]=y0+min(min(R.dp[0][0],R.dp[1][0])+min(x0,x1),
x1+x0+R.dp[1][0]-y1);
U.dp[1][1]=y0+min(min(R.dp[0][1],R.dp[1][1])+min(x0,x1),
x1+x0+R.dp[1][1]-y1);
return;
}
else if(leafR){//特判:右儿子是叶子节点
U.dp[0][0]=x0+x1+min(L.dp[0][0],L.dp[0][1]);
U.dp[1][0]=x0+x1+min(L.dp[1][0],L.dp[1][1]);
U.dp[0][1]=y1+min(min(L.dp[0][0],L.dp[0][1])+min(x0,x1),
x1+x0+L.dp[0][1]-y0);
U.dp[1][1]=y1+min(min(L.dp[1][0],L.dp[1][1])+min(x0,x1),
x1+x0+L.dp[1][1]-y0);
return;
}
for(int i=0;i<2;i++)//正常转移
for(int j=0;j<2;j++)
for(int c1=0;c1<2;c1++)
for(int c2=0;c2<2;c2++){
int tp=L.dp[i][c1]+R.dp[c2][j]+min(x0,x1);
U.dp[i][j]=min(U.dp[i][j],tp);
if(c1){
U.dp[i][j]=min(U.dp[i][j],tp-y0+max(x0,x1));
}
if(c2){
U.dp[i][j]=min(U.dp[i][j],tp-y1+max(x0,x1));
}
}
}
void pushup(int u){
pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r){
tr[u]=(tree){l,r};
if(l==r){
tr[u].init_INF();
tr[u].dp[1][1]=col[l];
return;
}
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
void modify(int u,int x){
if(tr[u].l==tr[u].r){
tr[u].init_INF();
tr[u].dp[1][1]=col[x];
return;
}
int mid=tr[u].l+tr[u].r>>1;
if(mid>=x)
modify(u<<1,x);
else
modify(u<<1|1,x);
pushup(u);
}
tree query(int u,int l,int r){
if(tr[u].l>=l&&tr[u].r<=r)
return tr[u];
int mid=tr[u].l+tr[u].r>>1;
if(mid>=r)return query(u<<1,l,r);
if(mid<l)return query(u<<1|1,l,r);
tree L=query(u<<1,l,r),R=query(u<<1|1,l,r),U;
pushup(U,L,R);
return U;
}
int n,m;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
scanf("%d",row1+i);
for(int i=1;i<n;i++)
scanf("%d",row2+i);
for(int i=1;i<=n;i++)
scanf("%d",col+i);
build(1,1,n);
char opt[2];
int x0,y0,x1,y1,w;
while(m--){
scanf("%s",opt);
if(opt[0]=='C'){
scanf("%d%d%d%d%d",&x0,&y0,&x1,&y1,&w);
if(x0!=x1){
col[y0]=w;
modify(1,y0);
}
else{
if(y0>y1)swap(y0,y1);
if(x0==1)
row1[y0]=w;
else
row2[y0]=w;
}
modify(1,y0);//修改了边权后需要从最深到根pushup一遍
}
else{
scanf("%d%d",&x0,&y0);
tree tp=query(1,x0,y0);
printf("%d\n",min(min(tp.dp[0][0],tp.dp[0][1]),min(tp.dp[1][0],tp.dp[1][1])));
}
}
return 0;
}
```