F. Fake Maxpooling
题意：
给你一个n * m的矩阵， 矩阵值为 行号 i 、 列号 j的lcm（最小公倍数）， 求这个n * m 矩阵所有 k * k 子矩阵中最大值的和。
思路：
单调队列求每行窗口k内的最大值，并记录到broad矩阵中， 在对broad矩阵每列用单调矩阵求一遍窗口k内的最大值， 把每个子矩阵的贡献加到起来就行了。
单调矩阵是什么，详解在这里
code：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 5;
int mp[maxn][maxn], broad[maxn][maxn]；
int qu[maxn], head, tail; //qu为但单调队列，head为前指针，tail为后指针int gcd(int n, int m){int t;while(m != 0){t = n % m;n = m; m = t;}return n;
}int main(){int n, m, k;scanf("%d%d%d", &n, &m, &k);for(int i = 1; i <= n; i++) //得到lcm矩阵for(int j = 1; j <= m; j++)mp[i][j] = i / gcd(i, j) * j; long long sum = 0;if(k > 1){for(int i = 1; i <= n; i++){head = 1;tail = 0;for(int j = 1; j <= m; j++){ //求每个子矩阵的最大值，用单调递减队列 //若求最小值用单调递增队列 if(tail < head) qu[++tail] = j;else {if(j >= k && qu[head] < j - k + 1) head++;while(tail >= head && mp[i][j] >= mp[i][qu[tail]]) tail--;qu[++tail] = j;}if(j >= k) broad[i][j] = mp[i][qu[head]]; }}for(int i = k; i <= m; i++){head = 1;tail = 0;for(int j = 1; j <= n; j++){if(tail < head) qu[++tail] = j;else {if(j >= k && qu[head] < j - k + 1) head++;while(tail >= head && broad[j][i] >= broad[qu[tail]][i]) tail--;qu[++tail] = j;}if(j >= k) sum += broad[qu[head]][i];}}}else {for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)sum += mp[i][j];}printf("%lld\n", sum);}