2019牛客暑期多校训练营（第三场）F Planting Trees

2019牛客暑期多校训练营（第三场）F Planting Trees

题意: 一个 N ∗ N N \ast N N∗N 的矩阵，问最大值和最小值大小差距不超过 M M M的最大子矩阵多大。

题解: 题目明示你要使用 O ( N 3 ) O(N^3) O(N3)的杂度,暴力枚举子矩阵高度 x x x，做一个预处理，把 a [ i ] [ j ] a[i][j] a[i][j]到 a [ i + x ] [ j ] a[i+x][j] a[i+x][j]的最大最小值处理出来，压缩成一行，然后做一次求区间最大值和最小值差值不超过 M M M的区间最大长度。

不懂单调队列的可以看看 单调栈和单调队列

#include "stdio.h"
#include "ctype.h"
  
#define max(a, b) a>b?a:b
#define min(a, b) a<b?a:b
const int maxn = 5e2 + 5;
  
struct deq {
    static const int start = maxn * 2;
    int dat[start * 2];
    int l = start;
    int r = start;
  
    void push_front(int x) {
        dat[l--] = x;
    }
  
    void pop_front() {
        l++;
    }
  
    int front() {
        return dat[l + 1];
    }
  
    void push_back(int x) {
        dat[++r] = x;
    }
  
    void pop_back() {
        r--;
    }
  
    int back() {
        return dat[r];
    }
  
    int size() {
        return r - l;
    }
  
    void clear() {
        r = l = start;
    }
  
    bool empty() {
        return r == l;
    }
};
  
deq dqmx, dqmi;
  
template<typename T>
void read(T &w) {  //读入
    char c;
    while (!isdigit(c = getchar()));
    w = c & 15;
    while (isdigit(c = getchar()))w = w * 10 + (c & 15);
}
  
int n, k;
int a[maxn][maxn];
int ans = 0;
int mi[maxn][maxn];
int mx[maxn][maxn];
  
  
int main() {
    int T;
    read(T);
    while (T--) {
        read(n);
        read(k);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                read(a[i][j]);
            }
        }
        ans = 0;
        for (int x = 1; x <= n; x++) {
            for (int i = n; i >= x; i--) {
                int pos = 0;
                dqmx.clear();
                dqmi.clear();
                for (int j = 1; j <= n; j++) {
                    if (x == 1) {
                        mx[i][j] = a[i][j];
                        mi[i][j] = a[i][j];
                    } else {
                        mx[i][j] = max(mx[i - 1][j], a[i][j]);
                        mi[i][j] = min(mi[i - 1][j], a[i][j]);
                    }
                    int tmi = mi[i][j], tmx = mx[i][j];
                    if (tmx - tmi > k) {
                        dqmi.clear();
                        dqmx.clear();
                        pos = j;
                    } else {
                        while (dqmi.size() && mi[i][dqmi.back()] > tmi) {
                            dqmi.pop_back();
                        }
                        dqmi.push_back(j);
                        while (dqmx.size() && mx[i][dqmx.back()] < tmx) {
                            dqmx.pop_back();
                        }
                        dqmx.push_back(j);
                        while (mx[i][dqmx.front()] - mi[i][dqmi.front()] > k) {
                            if (dqmx.front() < dqmi.front()) {
                                pos = dqmx.front();
                                dqmx.pop_front();
                            } else {
                                pos = dqmi.front();
                                dqmi.pop_front();
                            }
                        }
                        ans = max(ans, x * (j - pos));
                    }
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}