2019 牛客多校第二场 H - Second Large Rectangle

发表于 更新于 分类于 阅读次数：

题目链接：2019 牛客多校第二场 H

动态维护第\(i\)行的每一个元素\(s_{i,j}\)，向上最大能到达的高度\(h_j\)，向左能到达的最远点\(l_j\)，向右能到达的最远点\(r_j\)，满足\(l_j\)和\(r_j\)的\(h\)值都是大于等于\(h_j\)的。那么我们知道最大值是

\[ \max_{i = 1}^{n} \max_{j = 1}^{m} h_j \times (r_j - l_j + 1) \]

那么我们只要在\(h_j \times (r_j - l_j + 1)\)的基础上减去一行或者一列，以及\(h_j \times (r_j - l_j + 1)\)本身都存起来，排序去重后取第二个就是全局第二大。渐进时间复杂度\(O(n^2 \log n)\)。

这道题去重会卡 set。

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
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 1000 + 5;
int n, m;
char s[MAX_N][MAX_N];
int l[MAX_N], r[MAX_N], h[MAX_N];
struct Rectangle {
    int lx, ly, rx, ry, s;
    Rectangle(int lx_ = 0, int ly_ = 0, int rx_ = 0, int ry_ = 0, int s_ = 0)
        : lx(lx_), ly(ly_), rx(rx_), ry(ry_), s(s_) {}
    friend bool operator < (const Rectangle &u, const Rectangle &v) {
        if (u.s != v.s) return u.s > v.s;
        else {
            if (u.lx != v.lx) return u.lx < v.lx;
            else if (u.ly != v.ly) return u.ly < v.ly;
            else if (u.rx != v.rx) return u.rx < v.rx;
            else return u.ry < v.ry;
        }
    }
    friend bool operator == (const Rectangle &u, const Rectangle &v) {
        return u.lx == v.lx && u.ly == v.ly && u.rx == v.rx && u.ry == v.ry && u.s == v.s;
    }
    inline void debug() {
        printf("DEBUG LOG: lx = %d, ly = %d, rx = %d, ry = %d, s = %d\n", lx, ly, rx, ry, s);
    }
};
// set <Rectangle> uni;
int tot = 0;
Rectangle v[MAX_N * MAX_N * 5];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", &s[i][1]);
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s[i][j] == '1') ++h[j];
            else h[j] = 0;
        }
        h[0] = h[m + 1] = -1;
        int k;
        for (int j = 1; j <= m; ++j) {
            k = j;
            while (h[j] <= h[k - 1]) k = l[k - 1];
            l[j] = k;
        }
        for (int j = m; j >= 1; --j) {
            k = j;
            while (h[j] <= h[k + 1]) k = r[k + 1];
            r[j] = k;
        }
        // for (int j = 1; j <= m; ++j) printf("l = %d, r = %d, h = %d\n", l[j], r[j], h[j]);
        for (int j = 1; j <= m; ++j) {
            if (h[j] == 0) continue;
            ans = max(ans, h[j] * (r[j] - l[j] + 1));
            // uni.insert(Rectangle(i - h[j] + 1, l[j], i, r[j], h[j] * (r[j] - l[j] + 1)));
            v[++tot] = Rectangle(i - h[j] + 1, l[j], i, r[j], h[j] * (r[j] - l[j] + 1));
            if (r[j] - l[j] + 1 > 1) {
                int th = h[j], tl = r[j] - l[j]; int ts = th * tl;
                // uni.insert(Rectangle(i - h[j] + 1, l[j], i, r[j] - 1, ts));
                v[++tot] = Rectangle(i - h[j] + 1, l[j], i, r[j] - 1, ts);
                // uni.insert(Rectangle(i - h[j] + 1, l[j] + 1, i, r[j], ts));
                v[++tot] = Rectangle(i - h[j] + 1, l[j] + 1, i, r[j], ts);
            }
            if (h[j] > 1) {
                int th = h[j] - 1, tl = r[j] - l[j] + 1; int ts = th * tl;
                // uni.insert(Rectangle(i - h[j] + 2, l[j], i, r[j], ts));
                v[++tot] = Rectangle(i - h[j] + 2, l[j], i, r[j], ts);
                // uni.insert(Rectangle(i - h[j] + 1, l[j], i - 1, r[j], ts));
                v[++tot] = Rectangle(i - h[j] + 1, l[j], i - 1, r[j], ts);
            }
        }
    }
    // for (auto e: uni) e.debug();
    sort(v + 1, v + tot + 1);
    int uniTot = unique(v + 1, v + tot + 1) - v;
    // for (int i = 1; i < uniTot; ++i) v[i].debug();
    if (uniTot == 0 || uniTot == 1) puts("0");
    else {
        // uni.erase(uni.begin());
        printf("%d\n", v[2].s);
    }
    return 0;
}