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

题目描述

  Given a matrix of size and an integer , where , the least common multiple of and . You should determine the sum of the maximums among all submatrices.

输入描述

  Only one line containing three integers .

输出描述

  Only one line containing one integer, denoting the answer.

示例1

输入

3 4 2

输出

38  

说明

  The given matrix is: .
  The maximums among all submatrices are respectively, and their sum is .

分析

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

代码

/******************************************************************
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;
}