没想到线段树
Description.
有一个 \(2\times n\) 的网格，有 \(3\times n-2\) 条边。
需要支持边权修改，以及求区间最小生成树。
Solution.
就是考虑区间合并时，会多出来两条边，再找到最大的那条边删掉。
由于最小生成树必定存在
线段树强上。
分别维护
右边两条横边、选了几条竖边，最左边和最右边的竖边边权，左边、右边一圈的最小值，最小横边，答案
然后直接暴力维护即可。
Coding.
//是啊，你就是那只鬼了，所以被你碰到以后，就轮到我变成鬼了{{{
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
x=0;char c=getchar(),f=0;
for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
f?x=-x:x;
}/*}}}*/
const int N=60005;
int n,m,hg[N][2],rw[N];
struct node
{
int rhg0,rhg1,cnt,lsh,rsh,lvl,rvl,mx;ll res;
//分别为右边两条横边、选了几条竖边，最左边和最右边的竖边边权
//左边、右边一圈的最小值，最小横边，答案
inline node operator+(node b)
{
node a=*this,r;r.rhg0=b.rhg0,r.rhg1=b.rhg1,r.rsh=b.rsh,r.lsh=a.lsh;
int a1=a.rhg0,a2=a.rhg1,b1=a.rvl,b2=b.lvl,mx;
mx=max(max(a1,a2),max(b1,b2)),r.mx=max(max(a1,a2),max(a.mx,b.mx));
r.res=a.res+b.res+a1+a2-mx,r.lvl=a.lvl,r.rvl=b.rvl,r.cnt=a.cnt+b.cnt;
if(mx==b1)
{
if(a.rsh!=b1) return r;else if(a.cnt>1) return r.cnt--,r;
return r.cnt--,r.lsh=b.lsh,r.lvl=max(max(b.lvl,a.mx),max(a1,a2)),r;
}
if(mx==b2)
{
if(b.lsh!=b2) return r;else if(b.cnt>1) return r.cnt--,r;
return r.cnt--,r.rsh=a.rsh,r.rvl=max(max(a.rvl,b.mx),max(a1,a2)),r;
}
return r;
}
}T[N<<2];
inline node init(int x) {return(node){hg[x][0],hg[x][1],1,rw[x],rw[x],rw[x],rw[x],0,rw[x]};}
inline void pt(node x) {printf("%d,%d %d %d,%d,%d,%d %d ! %lld\n",x.rhg0,x.rhg1,x.cnt,x.lsh,x.rsh,x.lvl,x.rvl,x.mx,x.res);}
inline void build(int x,int l,int r)
{
if(l==r) return T[x]=init(l),void();
build(x<<1,l,(l+r)>>1),build(x<<1|1,((l+r)>>1)+1,r),T[x]=T[x<<1]+T[x<<1|1];
//pt(T[x<<1]),pt(T[x<<1|1]),pt(T[x]),putchar(‘\n‘);
}
inline void updat(int x,int l,int r,int dw)
{
if(l==r) return T[x]=init(l),void();
if(dw<=((l+r)>>1)) updat(x<<1,l,(l+r)>>1,dw),T[x]=T[x<<1]+T[x<<1|1];
else updat(x<<1|1,((l+r)>>1)+1,r,dw),T[x]=T[x<<1]+T[x<<1|1];
}
inline node query(int x,int l,int r,int dl,int dr)
{
int md;if(dl<=l&&r<=dr) return T[x];else md=(l+r)>>1;
if(dl>md) return query(x<<1|1,md+1,r,dl,dr);
else if(md>=dr) return query(x<<1,l,md,dl,dr);
return query(x<<1,l,md,dl,dr)+query(x<<1|1,md+1,r,dl,dr);
}
int main()
{
read(n),read(m);for(int i=1;i<n;i++) read(hg[i][0]);
for(int i=1;i<n;i++) read(hg[i][1]);
for(int i=1;i<=n;i++) read(rw[i]);
build(1,1,n);for(int x1,y1,x2,y2,vl;m--;)
{
char fg[5];scanf("%s",fg),read(x1);
if(*fg==‘Q‘) read(x2),printf("%lld\n",query(1,1,n,min(x1,x2),max(x1,x2)).res);
else
{
read(y1),read(x2),read(y2),read(vl);
if(y1==y2) rw[y1]=vl,updat(1,1,n,y1);
else hg[min(y1,y2)][x1-1]=vl,updat(1,1,n,min(y1,y2));
}
}
return 0;
}