2020牛客暑期多校训练营（第二场）F-Duration
/***************
题目来源：2020牛客暑期多校训练营（第二场）F-Duration题目链接：https://ac.nowcoder.com/acm/contest/5667/F 题目类型：单调队列 题目大意：n*m的矩阵，a[i][j]=gcd(i,j),求所有k阶子矩阵中最大元素的和 题目思路：先对行做单调队列，每k个元素的最大值记录下来，再对新数组的列用单调队列，记录每k个元素的最大值，求和即可题目总结：这道题目比较简单，前期思路是对的，但是由于学艺不精，忘记了单调队列可以求区间最大，导致这一步卡住，最终跑偏
****************/
#include<bits/stdc++.h>
using namespace std;
#define ll long longconst int maxn = 5005;
int a[maxn][maxn],b[maxn][maxn];int main()
{int n,m,k;ll ans=0;scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){a[i][j]=i*j/__gcd(i,j);}}deque<int>q;for(int i=1;i<=n;i++){q.clear();for(int j=1;j<=m;j++){while(q.size()&&q.front()<=j-k) q.pop_front();///如果队首元素的下标不属于区间范围，删掉 while(q.size()&&a[i][q.back()]<=a[i][j]) q.pop_back();///如果队尾元素小于准备更新的数，删掉（保持单调性） q.push_back(j);///压入队列（单调队列模板-max） b[i][j]=max(b[i][j],a[i][q.front()]);}}for(int j=k;j<=m;j++){q.clear();for(int i=1;i<=n;i++){while(q.size()&&q.front()<=i-k) q.pop_front();while(q.size()&&b[q.back()][j]<=b[i][j]) q.pop_back();q.push_back(i);if(i>=k) ans+=1ll*b[q.front()][j];}}printf("%lld\n",ans);return 0;
}