调差分调了半天...

观察数据，发现值域很小，矩形很多，需要转换成一个矩阵上的问题。

首先我们将几何上的矩形转换成矩阵的一个子矩阵，咋弄呢？你把平面直角坐标系每一个 $1\times 1$ 的小方块都按行按列编号成 $(x,y)$ 形式即可。

然后显然可以差分统计每个方块刷了多少次油漆，进一步得到有多少涂了 $k$ 次的方块，记录下来。

考虑我们添加的矩形对答案的贡献，对于 $k-1$ 有 $+1$ 的贡献，对于 $k$ 有 $-1$ 的贡献，我们问题变成找到两个无交的矩阵，使其和最大。

这是一个经典的问题，考虑枚举一行/一列将我们的数组切开，然后在彼此的区间各找一个最大区间。

我们处理 $f_{i,j}$ 表示以 $(i,j)$ 为左上角的最大矩阵，$g_{i,j}$ 表示以 $(i,j)$ 为右下角的最大矩阵。

$\mathcal O(n^3)$ 求法是很多的，我的做法是枚举一短横区间，把横区间内每一行的值的和都求出来，然后就变成了一个一维求最大区间的问题——对于我而言，我选择的左端点必然是前缀和最小的一项。

这么说有点抽象，可以参考代码理解。

利用这两项值可以求出 $F_{i,j}$ 表示 $(i,j)$ 左上角内的最大矩阵，$G_{i,j}$ 表示 $(i,j)$ 右下角内的最大矩阵。

这样切开之后就可以求出最大矩阵了。

时间复杂度为 $O(n^3)$，注意我说的 $n$ 是值域 $200$。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=200;
LL n,k,x,y,xx,yy,a[N+5][N+5],sum[N+5][N+5],ans2,ans,f[N+5][N+5],g[N+5][N+5],s[N+5];
LL cal(LL x,LL y,LL xx,LL yy)
{
	return sum[xx][yy]-sum[x-1][yy]-sum[xx][y-1]+sum[x-1][y-1];
}
int main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld%lld%lld",&x,&y,&xx,&yy);
		a[x+1][y+1]++,a[xx+1][yy+1]++;
		a[xx+1][y+1]--,a[x+1][yy+1]--;
	}
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=N;j++)
		{
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
		}
	}
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=N;j++)
		{
			if(sum[i][j]==k-1)a[i][j]=1;
			else if(sum[i][j]==k)ans2++,a[i][j]=-1;
			else a[i][j]=0;
		}
	}
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=N;j++)
		{
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
		}
	}
	memset(f,-127,sizeof(f));
	memset(g,-127,sizeof(g));
	for(int i=1;i<=N;i++)
	{
		for(int j=i;j<=N;j++)
		{
			LL mn=0;
			for(int x=1;x<=N;x++)
			{
				s[x]=s[x-1]+cal(x,i,x,j);
				f[x][j]=max(f[x][j],s[x]-mn);
				mn=min(s[x],mn);
			}
			mn=0;
			for(int x=N;x>=1;x--)
			{
				s[x]=s[x+1]+cal(x,i,x,j);
				g[x][i]=max(g[x][i],s[x]-mn);
				mn=min(s[x],mn);
			}
		}
	}
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=N;j++)
			f[i][j]=max({f[i-1][j],f[i][j-1],f[i][j]});
	}
	for(int i=N;i>=1;i--)
	{
		for(int j=N;j>=1;j--)
			g[i][j]=max({g[i+1][j],g[i][j+1],g[i][j]});
	}
	for(int i=2;i<=N;i++)
	{
		ans=max({ans,f[N][i-1]+g[1][i]});
	}
	for(int i=2;i<=N;i++)
	{
		ans=max({ans,f[i-1][N]+g[i][1]});
	}	
	printf("%lld",ans+ans2);
} 

我写的代码参考了梁意森的。这个做法颇为巧妙，有一些巧妙的小 trick。注意细节，比如区间边界什么的。

贴代码，思路略。

#include<bits/stdc++.h>
using namespace std;
int m,n=200,k,bs,ans,a[205][205],c[205][205],f[205][205],t[205];
int cal(int X1,int Y1,int X2,int Y2){
	return a[X2][Y2]-a[X1][Y2]-a[X2][Y1]+a[X1][Y1];
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>m>>k;
	for(int i=1;i<=m;i++){
		int X1,Y1,X2,Y2;
		cin>>X1>>Y1>>X2>>Y2;
		X1++,Y1++,X2++,Y2++;//坑了，题目里面是xy平面，题目说的左下角实际上是数组里的左上角 
//		swap(X1,X2); //不该这么做
		c[X1][Y1]++,c[X2][Y1]--,c[X1][Y2]--,c[X2][Y2]++;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			c[i][j]+=c[i-1][j]+c[i][j-1]-c[i-1][j-1];
			if(c[i][j]==k-1)a[i][j]=1;
			if(c[i][j]==k)a[i][j]=-1,bs++;
			a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
		}
	}
	for(int r=1;r<=n;r++){//注意以下矩阵左上角都是开的，并且l开r闭 
		for(int l=0;l<r;l++){
			int tmp=-0x3f3f3f3f,sum=0;
			if(l>0)t[l]=max(t[l],t[l-1]);//巧妙，这一步使得所有前面的t[]值都被拿来打擂台算答案了 
			for(int x=1;x<=n;x++)sum=max(0,sum)+cal(x-1,l,x,r),tmp=max(tmp,sum);
			ans=max(ans,tmp+t[l]),t[r]=max(t[r],tmp);
		}
	}
	memset(t,0,sizeof(t));
	for(int r=1;r<=n;r++){
		for(int l=0;l<r;l++){
			int tmp=-0x3f3f3f3f,sum=0;
			if(l>0)t[l]=max(t[l],t[l-1]);
			for(int y=1;y<=n;y++)sum=max(0,sum)+cal(l,y-1,r,y),tmp=max(tmp,sum);
			ans=max(ans,tmp+t[l]),t[r]=max(t[r],tmp);
		}
	}
	cout<<ans+bs;
	return 0;
}

https://blog.csdn.net/tenkuo/article/details/153389991?spm=1001.2014.3001.5502