题意：给定2行n列的四连通带权网格图，支持修改边权和查询第[l,r]列的最小生成树
题解：这是一道好题，要么SDOI2019中n=2的20pts怎么会“我抄我自己”？（当然NOIP2018“我抄我自己”除外，因为那是想给大家送分，而且NOIP2018的质量有多烂大家自己心里清楚）
对于区间[l,r]，其实只需维护第l列和第r列共4个点的连通性，以及满足连通的最小代价。维护的是MST最左、最右边的竖线位置，横线的最大值，左端点到最左边竖线中横线最大值，右端点到最右边竖线中横线的最大值，以及最小生成树（即答案）5个变量，建议开结构体。而情况比较多，讨论起来有些麻烦。
还有这道题要注意的是，每次从[l,r]应该递归到[l,mid][mid,r]两个区间，因为要维护的是连通块长度至少为2的连通块。
#include<bits/stdc++.h>
#define lson l,mid,rt<<1
#define rson mid,r,rt<<1|1
using namespace std;
const int N=;
struct node{int l,r,lmx,rmx,mx,s;}tr[N<<];
int n,m,c[N],v[N][];
void pushup(int rt,int lc,int rc)
{
tr[rt].mx=max(tr[lc].mx,tr[rc].mx);
tr[rt].s=tr[lc].s+tr[rc].s;
tr[rt].l=tr[lc].l,tr[rt].lmx=tr[lc].lmx;
tr[rt].r=tr[rc].r,tr[rt].rmx=tr[rc].rmx;
int mx=max(tr[lc].rmx,tr[rc].lmx);
if(tr[lc].r==tr[rc].l)tr[rt].s-=c[tr[lc].r];
else if(mx>=max(c[tr[lc].r],c[tr[rc].l]))tr[rt].s-=mx;
else if(c[tr[lc].r]>c[tr[rc].l])
{
tr[rt].s-=c[tr[lc].r];
if(tr[lc].l==tr[lc].r)tr[rt].l=tr[rc].l,tr[rt].lmx=max(tr[lc].mx,tr[rc].lmx);
}
else{
tr[rt].s-=c[tr[rc].l];
if(tr[rc].l==tr[rc].r)tr[rt].r=tr[lc].r,tr[rt].rmx=max(tr[rc].mx,tr[lc].rmx);
}
}
void build(int l,int r,int rt)
{
if(l+==r)
{
tr[rt].mx=max(v[l][],v[l][]);
if(tr[rt].mx>=max(c[l],c[r]))
{
tr[rt].l=l,tr[rt].r=r,tr[rt].lmx=tr[rt].rmx=;
tr[rt].s=v[l][]+v[l][]+c[l]+c[r]-tr[rt].mx;
}
else if(c[l]>c[r])
{
tr[rt].l=tr[rt].r=r,tr[rt].lmx=tr[rt].mx,tr[rt].rmx=;
tr[rt].s=v[l][]+v[l][]+c[r];
}
else{
tr[rt].l=tr[rt].r=l,tr[rt].rmx=tr[rt].mx,tr[rt].lmx=;
tr[rt].s=v[l][]+v[l][]+c[l];
}
return;
}
int mid=l+r>>;
build(lson),build(rson);
pushup(rt,rt<<,rt<<|);
}
void update(int L,int R,int l,int r,int rt)
{
if(L>R)return;
if(l+==r)
{
tr[rt].mx=max(v[l][],v[l][]);
if(tr[rt].mx>=max(c[l],c[r]))
{
tr[rt].l=l,tr[rt].r=r,tr[rt].lmx=tr[rt].rmx=;
tr[rt].s=v[l][]+v[l][]+c[l]+c[r]-tr[rt].mx;
}
else if(c[l]>c[r])
{
tr[rt].l=tr[rt].r=r,tr[rt].lmx=tr[rt].mx,tr[rt].rmx=;
tr[rt].s=v[l][]+v[l][]+c[r];
}
else{
tr[rt].l=tr[rt].r=l,tr[rt].rmx=tr[rt].mx,tr[rt].lmx=;
tr[rt].s=v[l][]+v[l][]+c[l];
}
return;
}
int mid=l+r>>;
update(L,min(R,mid),lson);
update(max(L,mid),R,rson);
pushup(rt,rt<<,rt<<|);
}
node query(int L,int R,int l,int r,int rt)
{
if(L==l&&r==R)return tr[rt];
int mid=l+r>>;
if(R<=mid)return query(L,R,lson);
if(L>=mid)return query(L,R,rson);
node u=query(L,mid,lson),v=query(mid,R,rson);
tr[(N<<)-]=u,tr[(N<<)-]=v;
pushup((N<<)-,(N<<)-,(N<<)-);
return tr[(N<<)-];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<n;i++)scanf("%d",&v[i][]);
for(int i=;i<n;i++)scanf("%d",&v[i][]);
for(int i=;i<=n;i++)scanf("%d",&c[i]);
build(,n,);
while(m--)
{
char op;cin>>op;
if(op=='Q')
{
int l,r;node u;scanf("%d%d",&l,&r);
if(l==r)printf("%d\n",c[l]);
else u=query(l,r,,n,),printf("%d\n",u.s);
}
else{
int x1,y1,x2,y2,z;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&z);
if(x1>x2)swap(x1,x2);
if(y1>y2)swap(y1,y2);
if(x1==x2)v[y1][x1-]=z;else c[y2]=z;
update(y1,y2,,n,);
}
}
}