Planting Trees

Posted on | In , , ,

题目链接

题意

找一个最大的子矩阵，使里面所有元素的大小之差不大于m。

思路

降维

通过枚举上边界，下边界，可以在O(n*n)的时间内得到每一列的最大值和最小值。

单调队列

用两个单调队列维护最大和最小，最大值递减，最小值递增，更新答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
#define inf 1ll << 50
 
const int N = 505;
int a[N][N];
int mxh[N], mnh[N];
int inc[N], decr[N];
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                scanf("%d", &a[i][j]);
        int ans = 0;
        for (int up = 1; up <= n; up++)
        {
            for (int j = 1; j <= n; j++)
                mxh[j] = 0, mnh[j] = 0x3f3f3f3f;
            for (int down = up; down <= n; down++)
            {
                //dbg(up, down);
                int pre = 0;
                int h1 = 0, h2 = 0, t1 = -1, t2 = -1;
                for (int j = 1; j <= n; j++)
                {
                    mxh[j] = max(mxh[j], a[down][j]);
                    mnh[j] = min(mnh[j], a[down][j]);
                    while (h1 <= t1 && mxh[decr[t1]] <= mxh[j])
                        t1--;
                    decr[++t1] = j;
                    while (h2 <= t2 && mnh[inc[t2]] >= mnh[j])
                        t2--;
                    inc[++t2] = j;
                    //dbg(t1, t2, decr[t1], inc[t2]);
                    while (h1 <= t1 && h2 <= t2 && mxh[decr[h1]] - mnh[inc[h2]] > m)
                    {
                    //  dbg(h1, h2, decr[h1], inc[h2]);
                        pre = min(decr[h1], inc[h2]);
                        if (decr[h1] < inc[h2])
                            h1++;
                        else if (decr[h1] > inc[h2])
                            h2++;
                        else
                        {
                            h1++;
                            h2++;
                        }
                    }
                    if (h1 <= t1 || h2 <= t2)
                        ans = max(ans, (down - up + 1) * (j - pre));
                    else
                        pre = j;
                    //dbg(j, pre, mxh[j], mnh[j], ans);
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

0%