AtCoder
写在前面
赛时没想出来，赛后经过大神和题解点拨有点思路了。之前确实没咋遇见过多少线段树维护矩阵的题。那就写写题解当积累trick了吧。
题意
给出一张\(3 \times N\) 的矩阵，内含# . 两种字符。其中# 代表该位置不能被经过，. 代表该位置能被经过。我们还有若干次操作，每次操作给出一个坐标，然后将这个坐标上的字符类型取反。我们可以向上下左右移动。求问在每次操作后从\((1,1)\) 到\((3,N)\) 需要走的最小步数是多少。若无法到达\((3,N)\) 则输出-1。
思路
赛时没有任何可行的思路，想过BFS等等乱七八糟的东西，但是由于有修改操作所以难以实现。但是其实正解的根本已经想到了，只不过不知道有这样的trick qwq。
我们注意到每次只会修改一个位置，而一个位置能影响的范围是有限的。比如修改一个位置状态无法使\((1,1)\) 到其左边点的步数改变。虽然能改变其右边点到\((3,N)\) 的步数，但是实际上从某个位置开始其无法再改变步数。所以修改一个位置的状态只会影响一个有限的区间，而幸运的是各个区间具有独立性和可合并性，然后我们就将本题转化为了一个区间修改和区间合并的问题。然后考虑用某种数据结构支持这种操作。那这就摆明了是线段树啊。
考虑线段树维护的信息。令\(t_{i,j,u}\) 为\(u\) 节点所代表的区间从最左边的第\(i\) 行到最右边的第\(j\) 行的最小步数。然后显然pushup的时候可以枚举中转点，即左儿子的右端点和右儿子的左端点，然后取所有端点中作为中转点答案最小的那个的答案即可。然后就能做到\(O(logn)\) 修改了。
然后初始化时就将. 代表的点点权赋为1，# 代表的点点权赋为INF。然后将线段树叶子节点赋为对应的点权或点权和即可。
对于查询，我们直接取\(t_{1,3,1}\) 的值即可。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10,inf=INT_MAX;
typedef long long ll;
int n,q;
ll a[4][maxn];
#define lc(u) (u<<1)
#define rc(u) (u<<1|1)
ll t[4][4][maxn<<2];
inline void pushup(int u){for(int i=1;i<=3;i++)for(int j=1;j<=3;j++){t[i][j][u]=inf;for(int k=1;k<=3;k++) t[i][j][u]=min(t[i][j][u],t[i][k][lc(u)]+t[k][j][rc(u)]);}
}
inline void build(int u,int l,int r){if(l==r){t[1][1][u]=a[1][l];t[2][2][u]=a[2][l];t[3][3][u]=a[3][l];t[1][3][u]=t[3][1][u]=a[3][l]+a[2][l]+a[1][l];t[1][2][u]=t[2][1][u]=a[2][l]+a[1][l];t[2][3][u]=t[3][2][u]=a[3][l]+a[2][l];return;}int mid=(l+r)>>1;build(lc(u),l,mid);build(rc(u),mid+1,r);pushup(u);
}
inline void update(int u,int l,int r,int p,int pos,int k){if(l==r){a[pos][l]=k;t[1][1][u]=a[1][l];t[2][2][u]=a[2][l];t[3][3][u]=a[3][l];t[1][3][u]=t[3][1][u]=a[3][l]+a[2][l]+a[1][l];t[1][2][u]=t[2][1][u]=a[2][l]+a[1][l];t[2][3][u]=t[3][2][u]=a[3][l]+a[2][l];return;}int mid=(l+r)>>1;if(p<=mid) update(lc(u),l,mid,p,pos,k);else update(rc(u),mid+1,r,p,pos,k);pushup(u);
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;char c;for(int i=1;i<=3;i++)for(int j=1;j<=n;j++)cin>>c,a[i][j]=(c=='.'?1:inf);a[1][1]=0;build(1,1,n);cin>>q;for(int i=1,x,y;i<=q;i++){cin>>x>>y;if(a[x][y]!=inf) update(1,1,n,y,x,inf);else update(1,1,n,y,x,1);cout<<(t[1][3][1]>=inf?-1:t[1][3][1])<<'\n';}return 0;
}