2019牛客暑期多校训练营（第三场）F Planting Trees(单调队列)

题目链接

大意：给你一个n*n的矩阵，让你求出面积最大的矩形，使得矩形内极差小于等于k
思路：我们枚举矩形上下界，然后遍历右边界，维护每列的最大最小值，同时维护两个个下标递增，值分别递增和递减的单调队列，每次弹出不合法的队头元素，然后更新答案即可。
细节见代码：

#include<bits/stdc++.h>
 
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define LL long long
#define SZ(X) X.size()
#define pii pair<int,int>
#define ALL(X) X.begin(),X.end()
 
using namespace std;
 
LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 2e5 + 11;
int t;
int n, k;
int A[555][555];
int L[555], R[555];
pii Li[555], Ri[555];
int main() {
    ios::sync_with_stdio(false);
    for (cin >> t; t; t--) {
        cin >> n >> k;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                cin >> A[i][j];
            }
        }
        LL ans = 0;
        for (int i = 1; i <= n; i++) {
            int need = 0;
            for (int p = 1; p <= n; p++)L[p] = 1e9, R[p] = 0;
            for (int j = i; j <= n; j++) {
                int a, b, c, d;
                a = b = c = d = 0;
                a = 1; c = 1;
                need = 0;
                for (int p = 1; p <= n; p++) {
                    L[p] = min(L[p], A[j][p]);
                    R[p] = max(R[p], A[j][p]);
                    if (p == 1) {
                        Li[1] = {L[1], 1};
                        Ri[1] = {R[1], 1};
                        b = d = 1;
                    } else {
                        while (a <= b && L[p] < Li[b].fi)b--;
                        while (c <= d && R[p] > Ri[d].fi)d--;
                        Li[++b] = {L[p], p};
                        Ri[++d] = {R[p], p};
                    }
                    while (a <= b && c <= d && Ri[c].fi > Li[a].fi + k) {
                        if (Ri[c].se <= Li[a].se)c++, need = max(need, Ri[c - 1].se);
                        else a++, need = max(need, Li[a - 1].se);
                    }
                    while (a <= b && Li[a].se <= need)a++;
                    while (c <= d && Ri[c].se <= need)c++;
                    ans = max(ans, 1ll * (j - i + 1) * (p - need));
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}