题目大意：给出三个参数n,m,k，构成元素为lcm(i,j)的n×m矩阵，求所有k×k子矩阵最大值之和。
做法：用一个长度为 k 的单调队列维护最大值，保持队列为单调递减。
压入数值之前，先将所有比之小的数值弹出（如果本身是最小且队列已满，则将队首元素弹出），然后压入数值，这样保证队首元素是该区间最大元素。
代码：
#include<bits/stdc++.h>
using namespace std;int lcm(int a,int b) //最小公倍数
{int ta = a,tb = b;int t = a%b;while(t){a = b;b = t;t = a%b;}return ta*tb/b;
}deque<int> dq; int mat[5005][5005];
int a[5005][5005];int main()
{int n,m,k;scanf("%d%d%d",&n,&m,&k);for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)mat[i][j] = lcm(i,j);for(int i = 1; i <= n; i++){dq.clear();dq.push_back(0);//为了程序正常运行for(int j = 1; j <= m; j++){if(j-dq.front() >= k) dq.pop_front();//如果队列满while(!dq.empty() && mat[i][j] >= mat[i][dq.back()])//先将比它小的元素弹出dq.pop_back();dq.push_back(j);a[i][j] = mat[i][dq.front()];}}long long ans = 0;for(int j = k; j <= m; j++){dq.clear();dq.push_back(0);for(int i = 1; i <= n; i++){if(i-dq.front() >= k)dq.pop_front();while(!dq.empty() && a[i][j] >= a[dq.back()][j])dq.pop_back();dq.push_back(i);if(i >= k)ans += a[dq.front()][j];}}cout << ans;return 0;
}