自动搬运

查看原文

来自洛谷，原作者为

	Time_tears oi复健ing

搬运于2025-08-24 22:17:25，当前版本为作者最后更新于2020-09-04 15:53:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

提供一篇 $O(200^3+n)$ 的题解

• 首先看完本题，一定知道直接对每个位置加 $1$ 是绝对没有出路的，所以我们首先需要用一个差分处理一下每个位置的值，这部分复杂度是 $O(200^2+n)$ 的。

• 然后，我们要想，什么样的位置会对 $answer$ 有影响呢$？$ 当然是值为 $k-1,k$ 的位置，首先我们用一个 $sum$ 记录下值为 $k$ 的位置数量。然后我们就发现，给区间加 $1$ 后，值为 $k$ 的位置贡献为 $-1$ ，值为 $k-1$ 的贡献为 $1$ ，然后我们枚举 $i,j$ 把第 $i$ 至 $j$ 的数给提出来，用一次最大连续子段和，这样就能求出以 $(i,j)$ 为右下节点的最大的值，再反过来做一次，就能求出以 $(i,j)$ 为左上节点的最大的值

• 因为是求两个区间，所以最后再用一次 dp 即可。

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include<cstdio>
#define N 205
using namespace std;
int k,e[N][N],f[N][N],d[N][N],ans;
int n,a[N][N],b[N][N],c[N][N],sum;
const int Mxdt=200000;
inline char gc() {
	static char buf[Mxdt],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxdt,stdin),p1==p2)?EOF:*p1++;
}
inline int read() {
	int res=0,bj=0;
	char ch=gc();
	while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=gc();
	while(ch>='0'&&ch<='9')res=(res<<3)+(res<<1)+(ch^48),ch=gc();
	return bj?-res:res;
}
inline int max(int x,int y) {
	return x>y?x:y;
}
int main() {
	n=read(),k=read();
	for(int i=1,x1,y1,x2,y2; i<=n; ++i)++a[x1=read()+1][y1=read()+1],++a[x2=read()+1][y2=read()+1],--a[x1][y2],--a[x2][y1];
	for(int i=1; i<=200; ++i)
		for(int j=1; j<=200; ++j) {
			a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1],b[i][j]=b[i][j-1];
			if(a[i][j]==k)--b[i][j],++sum;
			if(a[i][j]==k-1)++b[i][j];
		}
	for(int i=1; i<=200; ++i)
		for(int j=i; j<=200; ++j) {
			for(int k=1,len=0; k<=200; ++k)c[k][j]=max(c[k][j],len=max(0,len)+b[k][j]-b[k][i-1]);
			for(int k=200,len=0; k; --k)d[k][i]=max(d[k][i],len=max(0,len)+b[k][j]-b[k][i-1]);
		}
	for(int i=200; i; --i)
		for(int j=200; j; --j)f[i][j]=max(max(f[i+1][j],f[i][j+1]),d[i][j]);
	for(int i=1; i<=200; ++i)
		for(int j=1; j<=200; ++j)e[i][j]=max(max(e[i-1][j],e[i][j-1]),c[i][j]),ans=max(ans,sum+e[i][j]+max(f[i+1][1],f[1][j+1]));
	printf("%d",ans);
	return 0;
}