2019牛客暑期多校训练营（第三场）F 单调队列

题意

给一个\(n\times n\)的矩阵，找一个最大的子矩阵使其中最大值与最小值的差小于等于\(m\)。

分析

枚举子矩阵的上下边界，同时记录每一列的最大值和最小值。

然后枚举右边界，同时用两个单调队列分别维护最大值和最小值，考虑当右边界往右移动时，可行的最远的左边界一定是单调不减的，当枚举到第\(i\)列时且当前左边界为\(dl\)时，两个单调队列维护的分别是区间\([dl,i]\)的最大值和最小值，最大值-最小值>m时把左边界往右移，同时将单调队列中下标小于\(dl\)的值出队，直到得到可行的最远左边界，更新答案，复杂度为\(O(n^3)\)。

Code

#include<bits/stdc++.h>

#define fi first

#define se second

#define pb push_back

#define ll long long

using namespace std;

const int inf=1e9;

const int mod=1e9+7;

const int maxn=1e5+10;

int T;

int n,m;

int a[510][510];

int mx[510],mn[510],q1[510],q2[510];

int main(){

	scanf("%d",&T);

	while(T--){

		scanf("%d%d",&n,&m);

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

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

			scanf("%d",&a[i][j]);

		int ans=0;

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

			for(int j=1;j<=n;++j) mx[j]=mn[j]=a[i][j];

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

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

					mx[k]=max(mx[k],a[j][k]);

					mn[k]=min(mn[k],a[j][k]);

				}

				int l1=1,l2=1,r1=0,r2=0,dl=1;

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

					while(r1>=l1&&mn[q1[r1]]>=mn[k]) --r1;

					while(r2>=l2&&mx[q2[r2]]<=mx[k]) --r2;

					q1[++r1]=k;q2[++r2]=k;

					while(dl<=k&&mx[q2[l2]]-mn[q1[l1]]>m){

						dl++;

						while(l1<=r1&&dl>q1[l1]) l1++;

						while(l2<=r2&&dl>q2[l2]) l2++;

					}

					ans=max(ans,(j-i+1)*(k-dl+1));

				}

			}

		}

		printf("%lld\n",ans);

	}

	return 0;

}

巴特西

2019牛客暑期多校训练营（第三场）F 单调队列

题意

分析

Code

最新文章

热门文章