题解：P12019 [NOISG 2025 Finals] 洪水

· · 题解

分析

手模一下就能发现最终被淹没的区域一定是个矩形（否则一定有可拓展的点），有矩形就可以想到扫描线做法。首先找出所有可能有贡献的矩形，其边界外一定全为障碍，且内部不会被整行或整列的障碍。先枚举左边界 x 从 w 到 1 ，并在转移时顺便维护每个 (i, x) 最右连续障碍的长度和每行向下连续障碍的单调栈。对每个横向障碍找出其上下第一个长于自身的障碍，二分上界那行的向下连续障碍的单调栈以找出第一个不短于上下距离的竖直障碍，容易理解这种方法一定能枚举到所有可能矩形，个数是 \mathcal{O}(h \cdot w) 的。最后扫描线对每点求出最小覆盖矩形，扫描线易做，总时复 \mathcal{O}(h \cdot w \cdot (\log h + \log w)) 。

AC code

#include <bits/stdc++.h>

namespace io
{
  char buf[1 << 20], *p1(buf), *p2(buf), c;
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)

  template <typename _Tp> inline void read(_Tp& x)
  { x = 0; while (!isdigit(c = gc())); while (x = (x << 1) + (x << 3) + (c ^ 48), isdigit(c = gc())); }

  template <typename _Tp, typename... Args> inline void read(_Tp& x, Args&... args) { read(x), read(args...); }

  inline bool get(void) { while (!isdigit(c = gc())); return c ^ 48; }

  char pbuf[1 << 20], *pp(pbuf), sta[30], *top(sta);
#define flush() (fwrite(pbuf, 1, pp - pbuf, stdout), pp = pbuf)
#define pc(c) (pp - pbuf == 1 << 20 ? flush() : 0, *pp++ = (c))

  template <typename _Tp> inline void write(_Tp x)
  { while (*top++ = x % 10 ^ 48, x /= 10); while (pc(*--top), top != sta); }

  struct flusher { inline ~flusher(void) { flush(); } } ioflush;
} // namespace io

using io::read;
using io::get;
using io::write;

using u32 = int;

constexpr u32 N(5002);

u32 h, w, s[N][N], r[N], d[N], q[N][N], p[N][N], top[N], Q[N], tp; long long ans; std::bitset<N> mp[N];

struct rect
{
  u32 L, R, U, D, sz;
  inline rect(const u32& l, const u32& r, const u32& u, const u32& d)
  : L(l), R(r), U(u), D(d) { sz = (R - L + 1) * (D - U + 1); }
  friend inline bool operator < (const rect& a, const rect& b) { return a.sz > b.sz; }
}; std::vector<rect> in[N];

inline void Solve(const u32& L, const u32& U, const u32& D)
{
  static u32 ll, rr, m; if (D - U == 1) return; ll = 1, rr = top[U + 1];
  while (ll < rr) m = ll + rr + 1 >> 1, (q[U + 1][m] < D - U - 1) ? (rr = m - 1) : (ll = m);
  if (p[U + 1][ll] <= L + r[U] + 1 && p[U + 1][ll] <= L + r[D] + 1 && p[U + 1][ll] > L + 1)
    in[L + 1].emplace_back(L + 1, p[U + 1][ll] - 1, U + 1, D - 1);
}

struct segment_tree
{
  struct nd { u32 L, R; std::priority_queue<rect> rc; } tr[N << 2]; u32 cur, ql, qr; rect* qx;

#define Ls (i << 1)
#define Rs (Ls | 1)

  void build(const u32& i, const u32& l, const u32& r)
  { tr[i].L = l, tr[i].R = r; if (l != r) build(Ls, l, l + r >> 1), build(Rs, (l + r >> 1) + 1, r); }

  void modify(const u32& i)
  {
    if (ql <= tr[i].L && tr[i].R <= qr) { tr[i].rc.emplace(*qx); return; }
    if (ql <= tr[Ls].R) modify(Ls); if (tr[Rs].L <= qr) modify(Rs);
  }

  void query(const u32& i)
  {
    while (!tr[i].rc.empty() && tr[i].rc.top().R < cur) tr[i].rc.pop();
    if (!tr[i].rc.empty() && tr[i].rc.top().sz < qr) qr = tr[i].rc.top().sz;
    if (tr[i].L != tr[i].R) query((ql <= tr[Ls].R) ? Ls : Rs);
  }
} tr;

signed main(void)
{
#ifndef ONLINE_JUDGE
  freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
#endif

  u32 i, j, k, U, D;

  read(h, w); for (i = 1; i <= h; i++) for (j = 1; j <= w; j++) mp[i][j] = get();
  mp[0].set(), mp[h + 1].set(); for (i = 1; i <= h; i++) mp[i].set(0), mp[i].set(w + 1);

  for (i = w; ~i; i--)
  {
    for (j = 0; j <= h + 1; j++) mp[j][i + 1] ? (r[j]++) : (r[j] = 0);
    for (j = h; j; j--)
    {
      if (!mp[j][i + 1]) { d[j] = 0; continue; } d[j] = d[j + 1] + 1;
      while (top[j] && q[j][top[j]] <= d[j]) top[j]--;
      top[j]++, q[j][top[j]] = d[j], p[j][top[j]] = i + 1;
    }
    for (j = 1; j <= h; j++) if (mp[j][i])
    {
      U = D = j; while (D < h && mp[D + 1][i]) D++;
      for (k = U - 1, tp = 0; k <= D + 1; k++) if (r[k])
      { while (tp && r[Q[tp]] < r[k]) tp--; if (tp) Solve(i, Q[tp], k); Q[++tp] = k; }
      for (k = D + 1, tp = 0; k >= U - 1; k--) if (r[k])
      { while (tp && r[Q[tp]] < r[k]) tp--; if (tp && r[Q[tp]] > r[k]) Solve(i, k, Q[tp]); Q[++tp] = k; }
      j = D;
    }
  }

  for (i = 1, tr.build(1, 1, h); i <= w; i++)
  {
    for (rect& rc : in[i]) tr.ql = rc.U, tr.qr = rc.D, tr.qx = &rc, tr.modify(1);
    for (j = 1, tr.cur = i; j <= h; j++) if (!mp[j][i]) tr.ql = j, tr.qr = 3e7, tr.query(1), ans += tr.qr;
  }

  write(ans);

  return 0;
}