F. Fake Maxpooling（二维单调队列，类似筛法求lcm） 2020牛客暑期多校训练营（第二场）

本文主要是介绍F. Fake Maxpooling（二维单调队列，类似筛法求lcm） 2020牛客暑期多校训练营（第二场），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

题意：
$a [i] [j] = l c m (i, j)$
求所有 $k * k$ 小矩阵的最大值和。

思路：
维护横向单调队列求每一行的前 $k$ 个数最值，再用纵向单调队列求出纵向前 $k$ 个数最值。这样求出每一点对应 $k * k$ 矩阵的最值了。

但是本题求lcm是log，会被卡（虽然数据太弱，没有卡，但是到了5000就真的很慢）。题解用了类似筛法的方式，n^2的求出每一个位置的lcm，值得学习。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>using namespace std;typedef long long ll;const int maxn = 5000 + 7;
const int INF = 0x3f3f3f3f;int a[maxn][maxn],Gcd[maxn][maxn];
int n,m,k;struct Node {int id,x;
}q[20005];int gcd(int x,int y) {return y == 0 ? x : gcd(y,x % y);
}int lcm(int x,int y) {return x * y / gcd(x,y);
}void get1(int x) { //行最小int l = 1,r = 0;for(int i = 1;i < k;i++) {while(l <= r && q[r].x < a[x][i]) {r--;}q[++r] = {i,a[x][i]};}for(int i = k;i <= m;i++) {while(l <= r && q[r].x < a[x][i]) {r--;}q[++r] = {i,a[x][i]};while(i - q[l].id >= k) l++;a[x][i] = q[l].x;}
}void get2(int x) { //列最小int l = 1,r = 0;for(int i = 1;i < k;i++) {while(l <= r && q[r].x < a[i][x]) r--;q[++r] = {i,a[i][x]};}for(int i = k;i <= n;i++) {while(l <= r && q[r].x < a[i][x]) r--;q[++r] = {i,a[i][x]};while(i - q[l].id >= k) l++;a[i][x] = q[l].x;}
}int main() {scanf("%d%d%d",&n,&m,&k);for (int i = 1; i <= n; i ++) {for (int j = 1; j <= m; j ++) {if (!Gcd[i][j]) {for (int k = 1; k * i <= n && k * j <= m; k ++) {Gcd[k * i][k * j] = k, a[k * i][k * j] = i * j * k;}}}}for(int i = 1;i <= n;i++) get1(i);for(int i = 1;i <= m;i++) get2(i);ll ans = 0;for(int i = k;i <= n;i++) {for(int j = k;j <= m;j++) {ans += a[i][j];}}printf("%lld\n",ans);return 0;
}