Codeforces Round #578 (Div. 2) 二维差分 可做模板

题意： 在n*n的矩阵中，你可以选择一个k*k的子矩阵，然后将这个子矩阵中的所有B全部变为W，问你怎么选择这个子矩阵使得最终的矩阵中某一行全是W或者某一列全是W的个数最多

题解：考虑每一行和每一列，对于特定的一行来说，要想让其全变为W，那么子矩阵的左上角端点是在一个范围中的，因此我们可以把范围中的每一个值加1

为了速度选择用二维差分来做，最终矩阵中的最大值就是答案

此题可以作为二维差分模板

#include<bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

#define fore(i, s, t) for (int i = s; i < (int)t; i++)

#define fi first

#define se second

#define ll long long

using namespace std;

const int maxn=2e5+5;

const int inf=2e9;

int dif[2005][2005];//difference array

//from (x1,y1) (x2,y2) add val

void add(int x1,int y1,int x2,int y2,int val){

	dif[x1][y1]+=val;

	dif[x1][y2+1]-=val;

	dif[x2+1][y1]-=val;

	dif[x2+1][y2+1]+=val;

}

string s[maxn];

int main(){

	int n,k;

	cin>>n>>k;

	for(int i=0;i<n;i++){

		cin>>s[i];

	}

	int res=0;

	for(int i=0;i<n;i++){

		int l=-1,r=-1;

		for(int j=0;j<n;j++){

			if(s[i][j]=='B') {

				if(l==-1) l=j;

				r=j;

			}

		}

		if(l==-1) {

			res++;

			continue;

		}

		if(r-l+1>k) continue;

		add(max(1,i-k+2),max(1,r-k+2),i+1,l+1,1);

	}

	for(int j=0;j<n;j++){

		int l=-1,r=-1;

		for(int i=0;i<n;i++){

			if(s[i][j]=='B') {

				if(l==-1) l=i;

				r=i;

			}

		}

		if(l==-1) {

			res++;

			continue;

		}

		if(r-l+1>k) continue;

		add(max(1,r-k+2),max(j-k+2,1),l+1,j+1,1);

	}

	int ans=0;

	for(int i=1;i<=n;i++){

		for(int j=1;j<=n;j++){

			dif[i][j]=dif[i][j]+dif[i-1][j]+dif[i][j-1]-dif[i-1][j-1];

			ans=max(ans,dif[i][j]);

		}

	}

	printf("%d\n",ans+res);

}