2020牛客暑期多校训练营（第二场）F

类型

这道题很明显是一道单调队列的题目，这个数据结构在我之前的文章中有写到。

二维化一维

不过这是二维的，首先想到的是用一个单调队列来维护当前的最大值（如下图中que），由于对于每列来说只有该列的最大值是有用的，小于最大值的数不用理会（想想为什么），所以每列就存一个最大值就行，这样就变成了一维的了。

由于对不同行，计算新的连续K个排在一列的数（如图中蓝框）的最大值会重复遍历相同点，时间复杂度高，可以想到能不能先把最大值全算出来再利用。求连续K个排在一列的数的最大值其实又是一个求m区间内的最小值的问题，不过是对每一列求，这样每个点仅遍历一次就可求出所有位置的最大值。

做法：

对每一列用一次 求m区间内的最小值 的算法求出所有小矩形框对应最大值，再根据得到的最大值对每一行用 求m区间内的最小值 的算法求出每个矩阵对应的最大值。

C++代码：

#include<iostream>
using namespace std;
typedef long long ll;
const int MAX_N=5e3+5;
int arr[MAX_N][MAX_N];
int the_max[MAX_N][MAX_N];
int que[MAX_N];
int head=0,tail=0;

int gcd(int a,int b)
{
	return b?gcd(b,a%b):a;
}
void init(int n,int m)
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(!arr[i][j])arr[j][i]=arr[i][j]=i*j/gcd(i,j);	
}

int main()
{
	int n,m,k;//行n,列m 
	cin>>n>>m>>k;
	init(n,m);
	for(int j=1;j<=m;j++)
	{
		head=0,tail=0;
		for(int i=1;i<=k;i++)
		{
			while(head<tail&&que[tail-1]<arr[i][j])tail--;
			que[tail++]=arr[i][j];
		}
		the_max[1][j]=que[head];
		for(int i=k+1;i<=n;i++)
		{
			if(que[head]==arr[i-k][j])head++;
			while(head<tail&&que[tail-1]<arr[i][j])tail--;
			que[tail++]=arr[i][j];
			the_max[i-k+1][j]=que[head];
		}
	}
	long long ans=0;
	for(int i=1;i<=n-k+1;i++)//i行j列 
	{
		head=0,tail=0;
		for(int j=1;j<=k;j++)
		{
			while(head<tail&&que[tail-1]<the_max[i][j])tail--;
			que[tail++]=the_max[i][j];
		}
		ans += que[head];
		for(int j=k+1;j<=m;j++)
		{
			if(the_max[i][j-k]==que[head])head++;
			while(head<tail&&que[tail-1]<the_max[i][j])tail--;
			que[tail++]=the_max[i][j];
			ans+=que[head];
		}
	}
	cout<<ans;
	return 0;
}