题目描述
给出一个 n × n n\times n n×n 的矩形，每个格子被染成黑色或白色。
初始情况下，若 i + j i+j i+j 为奇数则 ( i , j ) (i,j) (i,j) 被染成黑色，否则 ( i , j ) (i,j) (i,j) 被染成白色。
现在有 k k k 个格子的颜色被改变了，即如果是黑色则变为白色，如果是白色则变为黑色。
现在你需要找出一个子矩形，使得矩形中黑色格子和白色格子数量差的绝对值最大，并输出这个值。
输入格式
第一行一个数 T T T，表示数据组数。
对于每组数据，第一行 2 2 2 个数 n , k n,k n,k。
接下来 k k k 行，每行 2 2 2 个数 x i , y i x_i,y_i xi,yi，表示一个颜色被改变的格子，保证每个格子至多出现 1 1 1 次。
样例
样例输入 1
3
3 1
1 1
3 4
1 2
2 1
2 3
3 2
3 4
1 1
1 3
3 1
3 3
样例输出 1
2
9
7
样例解释 1
对于第一组数据，
(
1
,
1
)
(1,1)
(1,1) 原本为白色，现在被染成了黑色，以
(
1
,
1
)
(1,1)
(1,1) 为左上角，
(
2
,
2
)
(2,2)
(2,2) 为右下角的矩形中共有
3
3
3 黑
1
1
1 白，答案为
3
−
1
=
2
3-1=2
3−1=2。
对于第二组数据，所有
9
9
9 个格子被染成了白色，答案为
9
−
0
=
9
9-0=9
9−0=9。
对于第三组数据，除了
(
2
,
2
)
(2,2)
(2,2) 的
8
8
8 个格子被染成了黑色，答案为
8
−
1
=
7
8-1=7
8−1=7。
数据范围
对于所有测试数据：
-
1 ≤ T ≤ 5 1\le T\le 5 1≤T≤5。
-
1 ≤ n ≤ 10 9 1\le n\le 10^9 1≤n≤109。
-
1 ≤ k ≤ 50 1\le k\le 50 1≤k≤50。
-
1 ≤ x i , y i ≤ n 1\le x_i,y_i\le n 1≤xi,yi≤n。
题解
因为
n
n
n 是
10
9
10^9
109，所以复杂度应该是和
k
k
k 有关的。
不难发现由于原图黑白相间，有偶数个点的话差值为
0
0
0，有奇数个点的话差值为
1
1
1。所以选择的矩形一定要包含某些修改点才能有意义。
那么不妨直接 k 2 k^2 k2 枚举修改点作为选取矩形的左上、右下顶点，然后对横纵坐标离散化后二维前缀和快速统计区域内的变化量。
但发现如果只枚举修改点作为顶点会有缺陷，因为若边长是偶数，我们再多选一行（列）使边长变为奇数，会使得某种颜色多一个，可能使得答案更优（简化枚举会漏掉一些在附近的边界情况）。
则我们可以考虑先遍历这 k k k 个点选出操作矩形，然后状压枚举四条边的向外扩展情况，这样是正确的。复杂度会有 4 × 4 = 16 4\times 4=16 4×4=16 的常数，不过由于 k ≤ 50 k\le 50 k≤50 可以接受。
注：不用管向内扩展的情况，是因为只有向外才有可能更优，且向内扩展的意思是不含某些点，这是不符合我们枚举含修改点的矩形的定义的。
实现细节见代码，包括枚举转化等。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node{
int x,y,xx,yy; //原坐标、离散化后坐标
};
void solve()
{
//输入+离散化
int n,k; cin>>n>>k;
vector<Node> p; vector<int> X,Y;
for(int i=0,x,y;i<k;i++){
cin>>x>>y; p.push_back({x,y,0,0});
X.push_back(x); Y.push_back(y);
}
sort(X.begin(),X.end()),X.erase(unique(X.begin(),X.end()),X.end()); sort(Y.begin(),Y.end()),Y.erase(unique(Y.begin(),Y.end()),Y.end());
int nx=X.size(),ny=Y.size();
vector<vector<int>> a(55,vector<int>(55));
for(int i=0;i<k;i++){
p[i].xx=lower_bound(X.begin(),X.end(),p[i].x)-X.begin(); //离散化后下标从0开始
p[i].yy=lower_bound(Y.begin(),Y.end(),p[i].y)-Y.begin();
a[p[i].xx][p[i].yy]=((p[i].x+p[i].y)&1)?1:-1;
// cerr<<i<<' '<<p[i].x<<' '<<p[i].y<<" -> "<<p[i].xx<<' '<<p[i].yy<<" ; "<<a[p[i].xx][p[i].yy]<<'\n';
}
//预处理前缀和
vector<vector<int>> s(55,vector<int>(55));
for(int i=0;i<nx;i++){
for(int j=0;j<ny;j++){
s[i+1][j+1]=s[i][j+1]+s[i+1][j]-s[i][j]+a[i][j]; //这里有一个别扭的点：前缀和如果也从0开始那么s[i-1],s[j-1]会越界，所以被迫从1开始
// cerr<<s[i+1][j+1]<<' ';
} //cerr<<'\n';
}
auto query=[&](int x1,int y1,int x2,int y2){
if(x1>x2||y1>y2) return 0;
return s[x2+1][y2+1]-s[x1][y2+1]-s[x2+1][y1]+s[x1][y1];
};
//开始操作
//细节：因为如果枚举左上、右下顶点的话仅保证横坐标有序，但纵坐标可能是乱的，还会有一些细节问题。所以从工程角度不妨直接从两个方向遍历4个坐标，效果等价
int ans=1; //至少可以只选一个格子，所以差值为1
for(int i=0;i<nx;i++){
int x1=X[i];
for(int j=i;j<nx;j++){
int x2=X[j];
for(int l=0;l<ny;l++){
int y1=Y[l];
for(int w=l;w<ny;w++){ //注意：i,j,l,w为离散化后的坐标；x1,x2,y1,y2是原始坐标 左上(i,l) 右下(j,w)
int y2=Y[w];
int S=query(i,l,j,w);
// cerr<<x1<<' '<<x2<<' '<<y1<<' '<<y2<<" ; "<<i<<' '<<j<<' '<<l<<' '<<w<<'\n';
int c=0;
if((x2-x1+1)%2==1&&(y2-y1+1)%2==1){ //只有长、宽都是奇数才会多一个格子，否则恰好抵消
c=((x1+y1)&1)?1:-1; //多的可以认为是左上角的格子
}
ans=max(ans,abs(c-2*S)); //意义：c为原始矩形的差值，-S是因为黑变白、白变黑是原来的反向操作，操作后的正确值应当取负，S乘2是因为1-(-1)=2
// cerr<<"a("<<x1<<' '<<y1<<' '<<x2<<' '<<y2<<") ("<<i<<' '<<l<<' '<<j<<' '<<w<<") "<<c<<' '<<S<<' '<<c-2*S<<'\n';
for(int mask=0;mask<(1<<4);mask++){ //从低到高对应：上、下、左、右
//扩展后的新坐标
int nx1=x1,nx2=x2,ny1=y1,ny2=y2;
int ni=i,nj=j,nl=l,nw=w;
if(mask>>0&1){ //上
if(x1-1<=0) continue;
nx1=x1-1;
if(i-1>=0&&X[i-1]==nx1) ni=i-1; //如果扩展后包含了新点，就在前缀和时也统计上
}
if(mask>>1&1){ //下
if(x2+1>n) continue;
nx2=x2+1;
if(j+1<nx&&X[j+1]==nx2) nj=j+1;
}
if(mask>>2&1){ //左
if(y1-1<=0) continue;
ny1=y1-1;
if(l-1>=0&&Y[l-1]==ny1) nl=l-1;
}
if(mask>>3&1){ //右
if(y2+1>n) continue;
ny2=y2+1;
if(w+1<ny&&Y[w+1]==ny2) nw=w+1;
}
S=query(ni,nl,nj,nw);
c=0;
if((nx2-nx1+1)%2==1&&(ny2-ny1+1)%2==1){
c=((nx1+ny1)&1)?1:-1;
}
ans=max(ans,abs(c-2*S));
// cerr<<"b("<<nx1<<' '<<ny1<<' '<<nx2<<' '<<ny2<<") ("<<ni<<' '<<nl<<' '<<nj<<' '<<nw<<") "<<c<<' '<<S<<' '<<c-2*S<<'\n';
}
// cerr<<"----------\n";
}
}
}
}
cout<<ans<<'\n';
}
signed main()
{
freopen("two.in","r",stdin);
freopen("two.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T; cin>>T; while(T--) solve();
return 0;
}
/*
hack:
1
4 6
1 3
1 4
3 2
3 3
4 2
4 3
Output:3
*/
转载自 CSDN-专业IT技术社区
