2019牛客多校第三场F-Planting Trees(单调队列)

Planting Trees

题目传送门

解题思路

枚举每一个下边界，再枚举其对应的所有上边界，求出其对应区间内的最大最小值，当下边界一样的时候，其最大最小值可以随着上边界减小逐步更新。然后将这些最大最小值分别放入单调队列，初始时设左边界为1，右边界即为当前放入的下标， 高即为此时枚举的高。当当前区间的最大最小值差超过m时，让最大值与最小值中位置靠前的出队，然后左边界变为其出队的下标+1。算出每一个满足条件的面积，取最大值即可。

代码如下

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

inline int read(){

    int res = 0, w = 0; char ch = 0;

    while(!isdigit(ch)){

        w |= ch == '-', ch = getchar();

    }

    while(isdigit(ch)){

        res = (res << 3) + (res << 1) + (ch ^ 48);

        ch = getchar();

    }

    return w ? -res : res;

}

const int N = 505;

int a[N][N];

int minn[N], maxx[N];

struct T{

    int i, val;

    T(int val, int i): val(val), i(i){}

};

int main()

{

    int t;

    scanf("%d", &t);

    while(t --){

        int n, m;

        n = read(), m = read();

        for(int i = 1; i <= n; i ++){

            for(int j = 1; j <= n; j ++)

                a[i][j] = read();

        }

        int ans = 0;

        for(int i = 1; i <= n; i ++){

            for(int j = i; j >= 1; j --){

                if(j == i){

                    for(int k = 1; k <= n; k ++)

                        minn[k] = maxx[k] = a[j][k];

                }

                else {

                    for(int k = 1; k <= n; k ++){

                        minn[k] = min(minn[k], a[j][k]);

                        maxx[k] = max(maxx[k], a[j][k]);

                    }

                }

                int dq1[N], dq2[N];

                int l1, r1, l2, r2;

                l1 = l2 = r1 = r2 = 0;

                int l = 1;

                for(int k = 1; k <= n; k ++){

                    while(l1 != r1 && minn[dq1[r1 - 1]] > minn[k])

                        -- r1;

                    while(l2 != r2 && maxx[dq2[r2 - 1]] < maxx[k])

                        -- r2;

                    dq1[r1 ++] = k;

                    dq2[r2 ++] = k;

                    while(l1 != r1 && l2 != r2 && maxx[dq2[l2]] - minn[dq1[l1]] > m){

                        int x1 = dq1[l1];

                        int x2 = dq2[l2];

                        l = min(x1, x2) + 1;

                        if(x1 <= x2)

                            l1 ++;

                        if(x1 >= x2)

                            l2 ++;

                    }

                    ans = max(ans, (i - j + 1) * (k - l + 1));

                }

            }

        }

        printf("%d\n", ans);

    }

    return 0;

}