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;
}