[ABC311] G - One More Grid Task

[Q] https://atcoder.jp/contests/abc311/tasks/abc311_g

考察
・解説の2ページ目を見る。CartesianTree()を習得した。
Q. CartesianTree？
A. 数列を、最小値の二分木にするアルゴリズム。処理はO(N)

A[] = {3, 1, 4, 1, 5}を考える。

・root
rootはA[1] = 1が最寄りの最小値なので、1。

・二分木G
以下のindex分けになる。
     1
   0   3
      2 4

G[1] = {0, 3}
G[3] = {2, 4}
となる。

・列の幅を全てのパターンで固定して、CartesianTreeで行の幅を得ることになる。
1. 次のように列の幅を固定する。mC2通り
[0, 1)、[0, 2), …, [0, M)
[1, 2), [1, 3,) …, [1, M)
…
2. 固定した列の範囲について。
行ごとの最小値をN要素の数列にする。CartesianTree()に投げる。
3. dfsで、行の最小値にあたるindexを取得しながら、面積を計算できる。

最も重いのは2の前処理。O(N*M^2)通りをすべて前計算しておく。

Q. これが分かれば、二次元グリッドで、最大の長方形の求め方もわかる？
A. 300*300盤面なら、A[]={0, 1}にすることで求まる。
けど、3000*3000盤面でも求まるアルゴリズムがありそう…。思いつかない。

実装

ll mins[310][310][310];
ll ranges[310][310][310];  // i, l, r
int main() {
  cincout();

  ll N, M;
  cin >> N >> M;
  vector<vector<ll>> A(N, vector<ll>(M));
  re(i, N) rep(j, M) cin >> A[i][j];

  // 最も重い。列の幅ごとに、最小値と総和を前計算しておく。[行][Left][Right]
  rep(i, N) rep(j, M) {
    ll m = A[i][j];
    for (ll k = j; k < M; ++k) {
      chmin(m, A[i][k]);
      mins[i][j][k + 1] = m;
      ranges[i][j][k + 1] = ranges[i][j][k] + A[i][k];
    }
  }
  ll ans = 0;
  vector<ll> B(N);
  vector<ll> acc(N);
  rep(j, M) for (ll k = j; k < M; ++k) { // 列を固定する。
    rep(i, N) { // 行の最小値を抽出して、CartesianTreeに投げる。
      B[i] = mins[i][j][k + 1];
      acc[i] = ranges[i][j][k + 1] + (i ? acc[i - 1] : 0);
    }
    auto [g, root] = CartesianTree(B);
    function<void(ll, ll, ll)> dfs = [&](ll l, ll r, ll d) {
      ll ac = acc[r - 1] - (l ? acc[l - 1] : 0);
      // cerr << j << "," << k << " " << l << "," << r << "," << d << " " << ac << " " << mins[d][j][k + 1] << " " << ac * mins[d][l][r] << endl;
      chmax(ans, ac * mins[d][j][k + 1]);
      for (auto to : g[d]) {
        if (to < d) { // rootより左側
          dfs(l, d, to);
        } else { // rootより右側
          dfs(d + 1, r, to);
        }
      }
    };
    dfs(0, N, root);
  }
  cout << ans << endl;
}

https://atcoder.jp/contests/abc311/submissions/44323604