P6100 [USACO19FEB] Painting the Barn G 题解

模拟赛碰到这道题的加强版，值域 $V=500$，花了 2h 切掉了，时间复杂度 $\mathcal{O}(V^3+V)$。

首先如果一个矩形都不加，那么答案就是涂了 $K$ 次的面积和，这个可以用二维差分维护。

我们考虑加一个矩形的情况，我的想法是维护一个二维前缀和，把涂了 $K$ 次的设为 $-1$，把涂了 $K-1$ 次的设为 $1$。

很容易想到枚举矩形的上界 $i$，下界 $j$ 用枚举 $k$ 记录前缀最小值做到 $O(V^3)$。

那现在考虑加两个矩形的情况，首先题目特意强调不相交，那么就是说可能增加的贡献都是覆盖了 $K-1$ 次的区域。

我们考虑用一条横线或一条竖线去劈这个区域把它分成两部分然后每一部分找一个最大的矩形。

然后这里卡了很久，一直想的是 $\mathcal{O}(V)$ 劈开然后按一个矩形的方法两边各做一次 $O(V^3)$，时间复杂度是 $\mathcal{O}(V^4)$ 的过不去。

然后发现其实我并不关心我具体选的哪两个矩形于是我们可以预处理，分横竖两个方向，以竖直方向的预处理为例，令 $mx1_k$ 表示纵坐标在 $[0,k]$ 的最大子矩形的值，$mx2_k$ 表示表示纵坐标在 $[k,V]$ 的最大子矩形的值，稍微用算一个矩形的代码改一下跑两遍就可以了，时间复杂度 $\mathcal{O}(V^3)$。

枚举竖线的位置 $l$，那么这种情况的答案就是 $mx1_l+mx2_{l+1}$，查询是 $\mathcal{O}(1)$ 的，再加上枚举的复杂度 $\mathcal{O}(V)$，查询总复杂度 $\mathcal{O}(V)$。

附上代码：

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const int MAXN = 5e2 + 10;
const int inf = 0x3f3f3f3f;
int n,K;
int mxx=0,mxy=0,mnx=500,mny=500;
int a[MAXN][MAXN],b[MAXN][MAXN];
int mx1[MAXN],mx2[MAXN],mx3[MAXN],mx4[MAXN];
int calc(int x1,int y1,int x2,int y2){
	int res=b[x2][y2];
	if(x1) res-=b[x1-1][y2];
	if(y1) res-=b[x2][y1-1];
	if(x1&&y1) res+=b[x1-1][y1-1];
	return res;
}
int main(){
//	freopen("paint.in","r",stdin);
//	freopen("paint.out","w",stdout);
	scanf("%d%d",&n,&K);
	FL(i,1,n){
		int x1,y1,x2,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		x2--,y2--;
		mnx=min({mnx,x1}),mny=min({mny,y1});
		mxx=max({mxx,x2}),mxy=max({mxy,y2});
		a[x1][y1]++,a[x1][y2+1]--,a[x2+1][y1]--,a[x2+1][y2+1]++;
	}
	int ans=0;
	FL(i,mnx,mxx){
		FL(j,mny,mxy){
			if(i>0) a[i][j]+=a[i-1][j];
			if(j>0) a[i][j]+=a[i][j-1];
			if(i>0&&j>0) a[i][j]-=a[i-1][j-1];
			if(a[i][j]==K-1) b[i][j]=1;
			if(a[i][j]==K) b[i][j]=-1,ans++;
		}
	}
	FL(i,mnx,mxx){
		FL(j,mny,mxy){
			if(i>0) b[i][j]+=b[i-1][j];
			if(j>0) b[i][j]+=b[i][j-1];
			if(i>0&&j>0) b[i][j]-=b[i-1][j-1];
		}
	}
	int mxa=-inf;
	FL(i,mnx,mxx){
		FL(j,i,mxx){
			int mn=0,now=0,tmp=0;
			FL(k,mny,mxy){
				now+=calc(i,k,j,k); 
				tmp=max(tmp,(now-mn));
				mx1[k]=max(mx1[k],tmp);
				mn=min(mn,now);
			}
			mn=0,now=0,tmp=0;
			FR(k,mxy,mny){
				now+=calc(i,k,j,k); 
				tmp=max(tmp,(now-mn));
				mx2[k]=max(mx2[k],tmp);
				mn=min(mn,now);
			}
			mxa=max(mxa,tmp);
		}
	}
	FL(i,mny,mxy){
		FL(j,i,mxy){
			int mn=0,now=0,tmp=0;
			FL(k,mnx,mxx){
				now+=calc(k,i,k,j); 
				tmp=max(tmp,(now-mn));
				mx3[k]=max(mx3[k],tmp);
				mn=min(mn,now);
			}
			mn=0,now=0,tmp=0;
			FR(k,mxx,mnx){
				now+=calc(k,i,k,j); 
				tmp=max(tmp,(now-mn));
				mx4[k]=max(mx4[k],tmp);
				mn=min(mn,now);
			}
			mxa=max(mxa,tmp);
		}
	}
	FL(l,mnx,mxx-1)
		mxa=max(mxa,mx3[l]+mx4[l+1]);
	FL(l,mny,mxy-1) 
		mxa=max(mxa,mx1[l]+mx2[l+1]);
	ans=ans+(mxa>0?mxa:0);
	printf("%d\n",ans);
}