CF1598E-Staircases【計數】

正題

題目連結:https://www.luogu.com.cn/problem/CF1598E

題目大意

給出一個\(n\times m\)的網格圖，開始所有都是黑色的，\(q\)次取反一個格子的顔色，然後求樓梯的數量。

樓梯定義為全黑色的下/右交替的格子集。

\(1\leq n,m\leq 1000,1\leq q\leq 10^4\)

解題思路

注意到其實是兩個斜行交錯，可以考慮把坐标軸旋轉\(45°\)，然後發現其實就是相鄰的兩行的正方形數量。

\(f_{i,j}\)表示格子\((i,j)\)所在斜行再往\((i,j)\)左上角的能延伸多少個黑色，然後每次\(O(n)\)暴力修改即可。

時間複雜度：\(O(qn)\)

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=1100;
ll n,m,q,w[N][N],a[N][N],ans;
ll calc(ll x,ll y)
{
	if(y<0)return 0;
	return min(x,y+1)+min(x,y);
}
signed main()
{
	scanf("%lld%lld%lld",&n,&m,&q);
	for(ll i=1;i<=n;i++)	
		for(ll j=1;j<=m;j++)
			w[i][j]=w[i-1][j-1]+1;
	for(ll i=1;i<=n;i++)
		for(ll j=1;j<=m;j++)
			ans+=calc(w[i][j],w[i-1][j])+calc(w[i][j],w[i][j-1])-1;
	while(q--){
		ll x,y;
		scanf("%lld%lld",&x,&y);
		if(a[x][y]){
			ll dx=x,dy=y;x++;y++;
			while(x<=n&&y<=m&&!a[x][y]){
				ans-=calc(w[x][y],w[x-1][y])+calc(w[x][y],w[x][y-1])-1;
				ans-=calc(w[x][y],w[x+1][y]-1)+calc(w[x][y],w[x][y+1]-1);
				x++;y++;
			}
			x=dx;y=dy;a[x][y]^=1;
			while(x<=n&&y<=m&&!a[x][y])
				w[x][y]=w[x-1][y-1]+1,x++,y++;
			x=dx;y=dy;
			while(x<=n&&y<=m&&!a[x][y]){
				ans+=calc(w[x][y],w[x-1][y])+calc(w[x][y],w[x][y-1])-1;
				ans+=calc(w[x][y],w[x+1][y]-1)+calc(w[x][y],w[x][y+1]-1);
				x++;y++;
			}
		}
		else{
			ll dx=x,dy=y;
			while(x<=n&&y<=m&&!a[x][y]){
				ans-=calc(w[x][y],w[x-1][y])+calc(w[x][y],w[x][y-1])-1;
				ans-=calc(w[x][y],w[x+1][y]-1)+calc(w[x][y],w[x][y+1]-1);
				x++;y++;
			}
			x=dx;y=dy;a[x][y]^=1;w[x][y]=0;x++;y++;
			while(x<=n&&y<=m&&!a[x][y])
				w[x][y]=w[x-1][y-1]+1,x++,y++;
			x=dx;y=dy;x++;y++;
			while(x<=n&&y<=m&&!a[x][y]){
				ans+=calc(w[x][y],w[x-1][y])+calc(w[x][y],w[x][y-1])-1;
				ans+=calc(w[x][y],w[x+1][y]-1)+calc(w[x][y],w[x][y+1]-1);
				x++;y++;
			}
		}
		printf("%lld\n",ans);
	}
}