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

https://ac.nowcoder.com/acm/contest/5667/F

思路：先把最小公倍数的素组求出来，利用单调队列求出每一行的最大值保存起来，然后再利用一次单调队列依次求出每一列的最大值加起来就是k阶子矩阵的最大值和。
单调队列（滑动窗口求最值）：比如有一个素组a，里面有几个数2，6，7，3，1，9.现在有一个长度为3的窗口从i=1的位置往右边移动，求每次移动时候窗口内数的最大值。我们队列里面保存的是入队元素的下标，可以认为队首保存的是当前窗口所在位置最大值的下标，入队时，判断入队元素与队尾元素值的大小，如果队尾元素比入队元素小，那么当前以及在有当前入队元素的位置，队尾元素的值都不可能是最大值，所以删除队尾元素然后入队，如果队尾元素的值比入队元素的值大，那么入队元素在之后窗口的位置还是有可能成为最大值的所以让其入队。

#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <stdio.h>
const int Max = 100 * 100 * 100 + 5;
#define LL long long
LL mod = 1e9+7;
const int INF = 1e5;
//const int inx = INT_MAX;
using namespace std;
//  srand(time(NULL));
//      m = rand() % 1000 + 1;
//定义i i(A) i+n i+n(B) i+n+n i+n+n(C)
//bitset<Max>s,q;

int gcd(int a,int b)
{
    if(b == 0) return a;
    else return gcd(b,a % b);
}

int lcm(int i,int j)
{
    return i / gcd(i,j) * j;
}

int a[5001][5001];
int b[5001][5001];
deque<int>q;
int main()
{
    int i,j,n,m,k;
    cin >> n >> m >> k;
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            a[i][j] = lcm(i,j);
        }
    }
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            while(!q.empty() && j - k >= q.front()){
                q.pop_front();
            }
            while(!q.empty() && a[i][j] >= a[i][q.back()]){
                q.pop_back();
            }
            q.push_back(j);
            if(j >= k) b[i][j] = a[i][q.front()];
        }
        q.clear();
    }
//    for(i = 1; i <= n; i++){
//        for(j = k; j <= m; j++){
//            cout << a[i][j] << " ";
//        }
//        cout << endl;
//    }
//    for(i = 1; i <= n; i++){
//        for(j = k; j <= m; j++){
//            cout << b[i][j] << " ";
//        }
//        cout << endl;
//    }
    LL sum = 0;
    for(i = k; i <= m; i++){
        for(j = 1; j <= n; j++){
            while(!q.empty() && j - k >= q.front()){
                q.pop_front(); 
            }
            while(!q.empty() && b[j][i] >= b[q.back()][i]){
                q.pop_back();
            }
            q.push_back(j);
            if(j >= k) sum += b[q.front()][i];
        }
        q.clear();
    }
    cout << sum;
    return 0;
}