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

题目描述

Given a matrix of size $n\times m$ and an integer $k$ , where $a_{i,j} = \mathrm{lcm}(i, j)$ , the least common multiple of $i$ and $j$ . You should determine the sum of the maximums among all $k\times k$ submatrices.

输入描述

Only one line containing three integers $n,m,k$ $(1\leqslant n,m \leq 5000, 1 \leqslant k \leqslant$ $\min(n, m))$ .

输出描述

Only one line containing one integer, denoting the answer.

示例1

输入

3 4 2

输出

说明

The given matrix is: $\begin{pmatrix}1&2&3&4\\2&2&6&4\\3&6&3&12\end{pmatrix}$ .
The maximums among all $2\times 2$ submatrices are $2,6,6,6,6,12$ respectively, and their sum is $38$ .

分析

要求所有边长为 $k$ 的正方形区域内的最值，可以看作将滑动窗口由一维的数轴扩展到了二维矩阵上。
首先对于每一行利用单调队列求出位于 $(i,j)$ 时， $(i,j)\sim (i,j+k-1)$ 区域内的最大值，用 $ans_{i,j}$ 表示。然后，遍历每一列，利用单调队列求出位于 $(i,j)$ 时， $(i,j)\sim (i+k-1,j)$ 区域内 $ans$ 的最大值，用 $ans_{i,j}$ 表示（直接赋值于 $ans_{i,j}$ ）；由于 $ans_{i,j}$ 已经是 $(i,j)\sim (i,j+k-1)$ 的最大值，所以第二次纵向求区间最大值后， $ans_{i,j}$ 已经表示由 $(i,j)$ 为左上角， $(i+k-1,j+k-1)$ 为右下角的正方形区域内的最大值。
至此，求出了所有边长为 $k$ 的正方形区域内的最值。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第二场） Problem F
Date: 8/11/2020
Description: Monotonous Queue
*******************************************************************/
#include<iostream>
#include<algorithm>
using namespace std;
const int N=5003;
int n,m,k;
int ans[N][N];
int a[N][N];
int q[N];
int head,tail;
int main()
{
    int i,j;
    cin>>n>>m>>k;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            a[i][j]=i*j/__gcd(i,j);
        }
    }
    for(i=1;i<=n;i++)
    {
        //第i行区间长度为k的区间最大值
        head=1;
        tail=0;
        for(j=1;j<=m;j++)
        {
            while(head<=tail&&a[i][q[tail]]<=a[i][j]) tail--;
            q[++tail]=j;
            while(head<=tail&&q[head]<=j-k) head++;
            if(j>=k) ans[i][j-k+1]=a[i][q[head]];
        }
    }
    for(j=1;j<=m;j++)
    {
        //考察每一列
        //已经是从i开始的横向长度为k的区间最大值
        //求从第j列开始的纵向长度为k的区间最大值
        //便有从(i,j)开始的区域边长为k的区间最大值
        head=1;
        tail=0;
        for(i=1;i<=n;i++)
        {
            while(head<=tail&&ans[q[tail]][j]<=ans[i][j]) tail--;
            q[++tail]=i;
            while(head<=tail&&q[head]<=i-k) head++;
            if(i>=k) ans[i-k+1][j]=ans[q[head]][j];
        }
    }
    long long tot=0;
    for(i=1;i<=n-k+1;i++)
    {
        for(j=1;j<=m-k+1;j++)
        {
            tot+=ans[i][j];
        }
    }
    cout<<tot<<endl;
    return 0;
}