F Fake Maxpooling（2020牛客暑期多校训练营（第二场））（单调队列）

F Fake Maxpooling（2020牛客暑期多校训练营（第二场））（单调队列）

链接：https://ac.nowcoder.com/acm/contest/5667/F
时间限制：C/C++ 3秒，其他语言6秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

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

输入描述:

Only one line containing three integers $n,m,k~(1\leq n,m \leq 5000, 1 \leq k \leq \min\{n, m\})$n,m,k (1≤n,m≤5000,1≤k≤min{n,m}).

输出描述:

Only one line containing one integer, denoting the answer.

示例1

输入

3 4 2

输出

38

说明

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

题解

官方题解：

我的做法：
利用LCM求出原始矩阵，时间 $O(n^2 logn)$O(n2logn)。题解说暴力求矩阵有可能会超时，不过我没超时[滑稽]
利用单调队列我们可以 $O(n^2)$O(n2) 的时间内求出保存区域最大值的矩阵，然后再 $O(n^2)$O(n2) 的时间内求出矩阵的和即可。

关于单调队列，其可以利用一个双端队列或者链表维护一个队列，队列内保存了一段区间内的最大值、次大值以及第三大值等等。其内部的值按照从大到小排序。枚举每一个区间（即类似于左右指针不断同时后移），那么队列内的首部值就是当前区间内的最大值，区间移动会加入新的值，把这个新加入的值不断地与队尾元素比较，如果比队尾元素大，就代表当前值可以替换掉队尾元素值，此时弹出队尾元素。当区间向后移动，首部值不属于当前有效区间时弹出，此时次大值成为新的最大值。

单调队列求区域最大值矩阵时，可以先枚举每一行，求出每一行的区域最大值。然后再枚举 每一列，在以上基础上求出每一列的区域最大值即求出小矩形区域内的最大值。

代码

#include <bits/stdc++.h>
#define m_p make_pair
#define _for(i, a) for(register int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for(register int i = (a), lennn = (b); i <= lennn; ++i)
using namespace std;
typedef long long LL;
const int maxn = 5005;
 
int n, m, k;
LL a[maxn][maxn];
deque<LL> dq;
 
inline LL lcm(LL a, LL b) {
    return a * b / __gcd(a, b);
}
 
inline void init() {
    _rep(i, 1, n) {
        _rep(j, 1, m) {
            if(!a[j][i]) a[i][j] = lcm(i, j);
            else a[i][j] = a[j][i];
        }
    }
}
 
void sol() {
    init();
    _rep(i, 1, n) {
        dq.clear();
        _rep(j, 1, m) {
            while(dq.size() && dq.front() < j - k + 1) dq.pop_front();
            while(dq.size() && a[i][dq.back()] <= a[i][j]) dq.pop_back();
            dq.push_back(j);
            a[i][j] = a[i][dq.front()];
        }
    }
    _rep(j, 1, m) {
        dq.clear();
        _rep(i, 1, n) {
            while(dq.size() && dq.front() < i - k + 1) dq.pop_front();
            while(dq.size() && a[dq.back()][j] <= a[i][j]) dq.pop_back();
            dq.push_back(i);
            a[i][j] = a[dq.front()][j];
        }
    }
    LL sum = 0;
    _rep(i, k, n) {
        _rep(j, k, m) {
            sum += a[i][j];
        }
    }
    cout << sum << "\n";
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    while(cin>>n>>m>>k) {
        sol();
    }
    return 0;
}