数据结构 线段树 P5618题解

· · 题解

有坑，但是不难（

看到题的第一眼使用线段树，对区间维护两个状态，上面和下面是否连通。

然后你发现会被环给 gank 掉。

于是重新设状态，设 w_{0/1,0/1} 表示左右端点中，上下节点是否连通。

这个相当好转移，只需要考虑合并的位置是否处于同一个连通块然后决定加上 x+y 还是 \min(x,y) 即可。

复杂度 O(m\log n) 比那个在环上删边的状态不知道高到哪里去了

#include<cstdio>
#include<cctype>
const int M=6e4+5;
int n,m,w1[M],w2[M];
inline char read_c(){
    char s;while(!isalpha(s=getchar()));return s;
}
inline int read(){
    int n(0);char s;while(!isdigit(s=getchar()));while(n=n*10+(s&15),isdigit(s=getchar()));return n;
}
inline void write(int n){
    static char s[15];int top(0);while(s[++top]=n%10^48,n/=10);while(putchar(s[top]),--top);putchar(10);
}
struct data{
    int w[2][2];
    inline int*operator[](const int&x){
        return w[x];
    }
}t[M<<2];
inline int min(const int&a,const int&b){
    return a>b?b:a;
}
inline data Merge(data a,const int&x,const int&y,data b){
    data ans;
    ans[0][0]=min(a[0][1]+b[1][0]+min(x,y),min(a[0][0]+b[1][0],a[0][1]+b[0][0])+x+y);
    ans[1][0]=min(a[1][1]+b[1][0]+min(x,y),min(a[1][0]+b[1][0],a[1][1]+b[0][0])+x+y);
    ans[0][1]=min(a[0][1]+b[1][1]+min(x,y),min(a[0][0]+b[1][1],a[0][1]+b[0][1])+x+y);
    ans[1][1]=min(a[1][1]+b[1][1]+min(x,y),min(a[1][0]+b[1][1],a[1][1]+b[0][1])+x+y);
    return ans;
}
inline void update(const int&u,const int&L,const int&R){
    const int&mid=L+R>>1;t[u]=Merge(t[u<<1],w1[mid],w2[mid],t[u<<1|1]);
}
inline void Build(const int&u,const int&L=1,const int&R=n){
    if(L==R)return void(t[u][1][1]=read());
    const int&mid=L+R>>1;Build(u<<1,L,mid);Build(u<<1|1,mid+1,R);update(u,L,R);
}
inline void Mdf(const int&u,const int&x,const int&w,const int&L=1,const int&R=n){
    if(L==R)return void(t[u][1][1]=w);
    const int&mid=L+R>>1;x<=mid?Mdf(u<<1,x,w,L,mid):Mdf(u<<1|1,x,w,mid+1,R);update(u,L,R);
}
inline void Update(const int&u,const int&x,const int&L=1,const int&R=n){
    const int&mid=L+R>>1;if(x!=mid)x<=mid?Update(u<<1,x,L,mid):Update(u<<1|1,x,mid+1,R);update(u,L,R);
}
inline data Qry(const int&u,const int&l,const int&r,const int&L=1,const int&R=n){
    if(l<=L&&R<=r)return t[u];
    const int&mid=L+R>>1;if(r<=mid)return Qry(u<<1,l,r,L,mid);if(l>mid)return Qry(u<<1|1,l,r,mid+1,R);
    return Merge(Qry(u<<1,l,r,L,mid),w1[mid],w2[mid],Qry(u<<1|1,l,r,mid+1,R));
}
signed main(){
    n=read();m=read();for(int i=1;i<n;++i)scanf("%d",w1+i);for(int i=1;i<n;++i)scanf("%d",w2+i);Build(1);
    for(int i=1;i<=m;++i){
        char s=read_c();
        if(s=='C'){
            int x0,y0,x1,y1;x0=read();y0=read();x1=read();y1=read();
            if(y0==y1)Mdf(1,y0,read());else(x0==1?w1:w2)[min(y0,y1)]=read(),Update(1,min(y0,y1));
        }
        if(s=='Q'){
            int L,R;L=read();R=read();write(Qry(1,L,R)[1][1]);
        }
    }
}