abc429f题解

liuziqin · 2025-10-26 21:47:59 · 题解

线段树大法好！

思路

首先有一个显然的结论，那就是最优路线一定不会往回走。

对于不修改的情况，考虑 dp。设 f_{i,j} 表示从 (1,1) 到 (j,i) 的最短路径。此时有转移方程 f_{i,j}=f_{i-1,k}+|k-j|。

现在带上修改操作，考虑将 dp 放到线段树上进行维护，对于一段区间 [l,r] 我们设 f_{x,y} 表示从 (x,l) 到 (y,r) 的最短路径，合并时转移方程即为 f_{x,y}=fl_{x,k}+fr_{k,y}+1。

最后考虑初始化。显然对于一列中 x 到达 y 时如果中间没有障碍物，代价即为 |x-y|，有就设为 +\infty 即可。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
const int INF=1e9;
char w[N][3];
struct node{
    int dp[3][3];
    void init(int x){
        for(int i=0;i<3;i++)
        for(int j=0;j<3;j++){
            dp[i][j]=abs(i-j);
            for(int k=min(i,j);k<=max(i,j);k++)if(w[x][k]=='#')dp[i][j]=INF;
        }
    }
};
node operator +(node a,node b){
    node ans;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++){
        ans.dp[i][j]=INF;
        for(int k=0;k<3;k++)
            ans.dp[i][j]=min(ans.dp[i][j],a.dp[i][k]+b.dp[k][j]+1);
    }
    return ans;
}
struct segtree{
    node sum[N<<2];
    void pushup(int p){
        sum[p]=sum[p*2]+sum[p*2+1];
    }
    void build(int p,int l,int r){
        if(l==r){
            sum[p].init(l);
            return ;
        }
        int mid=(l+r)>>1;
        build(p*2,l,mid);
        build(p*2+1,mid+1,r);
        pushup(p);
    }
    void add(int p,int l,int r,int x,int v){
        if(l==r){
            if(w[l][v]=='#')w[l][v]='.';
            else w[l][v]='#';
            sum[p].init(l);
            return ;
        }
        int mid=(l+r)>>1;
        if(mid>=x)add(p*2,l,mid,x,v);
        else add(p*2+1,mid+1,r,x,v);
        pushup(p);
    }
    int query(){
        return sum[1].dp[0][2];
    }
}st;
int main(){
    int n;
    cin>>n;
    for(int i=0;i<3;i++)
    for(int j=1;j<=n;j++)cin>>w[j][i];
    st.build(1,1,n);
    int q;
    cin>>q;
    while(q--){
        int x,y;
        cin>>x>>y;
        st.add(1,1,n,y,x-1);
        if(st.query()>=INF)cout<<"-1\n";
        else cout<<st.query()<<"\n";
    }
}