P8164 [JOI 2022 Final] 沙堡 2 题解

Description

JOI 君在沙滩上堆沙堡，他已经做好了一个沙堡，沙堡可以使用一个 $H\times W$ 的二维矩形表示，其被划分成若干个 $1\times 1$ 的小格子，格子高度互相不同。

JOI 君决定在沙堡上游走，他可以从任意一个点出发，向上下左右四个方向行走，必须满足他行走的路径单调下降。

出于一些原因，JOI 君想知道，在他所有可能的行走路径中，恰好覆盖了一个子矩形的路径数有多少条。

对于全部数据，$H,W\ge 1$，$HW\le 5\times 10^4$，$1\le A_{i,j}\le 10^7$，$A_{i,j}$ 互不相同。

Solution

首先一个子矩形合法的条件为子矩形内的每个点 $(i,j)$，都满足其值域上的前驱和后继都与其相邻。

但是直接暴力判断最多只做到 $O\left(H^3W^2\right)$，过不了。

考虑对每个点构造一个权值，使得这些权值的和为一个定值。

令 $X$ 为一个极大值，$v_{i,j}$ 表示 $(i,j)$ 的权值，$w_{i,j}$ 表示 $(i,j)$ 四周小于 $a_{i,j}$ 的最大权值，如果没有则为 $0$。如果 $a_{i,j}$ 大于其四周的数，则 $v_{i,j}=X-w_{i,j}$，否则 $v_{i,j}=a_{i,j}-w_{i,j}$。

容易发现一个合法矩形的所有 $v_{i,j}$ 的和为 $X$，证明就考虑如果每个点向周围比它大的最大位置连边，会连出一个内向树森林，而 $v_{i,j}$ 实际上是把每个内向树划分成若干条链，每条链的权值为 $X$，所以总权值为 $X$ 乘以链数，于是矩形合法的条件即为总权值为 $X$。

枚举矩形的上下边界和右端点，并在枚举的过程中维护每个位置的权值，用哈希表记录某个前缀的权值即可。

时间复杂度：$O(H^2W)$。

Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define int int64_t

const int kMaxT = 5e4 + 5, kInf = 1e10;
const int kD[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

int n, m, t;
int unq[kMaxT], sum[kMaxT], valt1[kMaxT], valt2[kMaxT], valt3[kMaxT];
std::vector<std::vector<int>> a, val1, val2, val3;

void init(std::vector<std::vector<int>> &v, int n = ::n, int m = ::m) {
  v.resize(n + 2, std::vector<int>(m + 2));
}

int getid(int x) {
  return std::lower_bound(unq + 1, unq + 1 + t, x) - unq;
}

void discrete() {
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      unq[++t] = a[i][j];
  std::sort(unq + 1, unq + 1 + t);
  t = std::unique(unq + 1, unq + 1 + t) - (unq + 1);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      a[i][j] = getid(a[i][j]);
}

void work() {
  std::swap(n, m);
  std::vector<std::vector<int>> b(n + 1, std::vector<int>(m + 1));
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      b[i][j] = a[j][i];
  a = b;
}

int getval1(int l, int r, int x, int y) {
  int mx = 0, _mx = 0;
  for (auto [dx, dy] : kD) {
    int tx = x + dx, ty = y + dy;
    if (tx >= l && tx <= r && ty >= 1 && ty <= m) {
      if (a[tx][ty] > a[x][y]) mx = std::max(mx, a[tx][ty]);
      if (a[tx][ty] < a[x][y]) _mx = std::max(_mx, a[tx][ty]);
    }
  }
  if (!mx) mx = kInf;
  else mx = a[x][y];
  return mx - _mx;
}

int getval2(int l, int r, int x, int y) {
  int mx = 0, _mx = 0;
  for (auto [dx, dy] : kD) {
    int tx = x + dx, ty = y + dy;
    if (tx >= l && tx <= r && ty >= 1 && ty <= m && dy != -1) {
      if (a[tx][ty] > a[x][y]) mx = std::max(mx, a[tx][ty]);
      if (a[tx][ty] < a[x][y]) _mx = std::max(_mx, a[tx][ty]);
    }
  }
  if (!mx) mx = kInf;
  else mx = a[x][y];
  return mx - _mx;
}

int getval3(int l, int r, int x, int y) {
  int mx = 0, _mx = 0;
  for (auto [dx, dy] : kD) {
    int tx = x + dx, ty = y + dy;
    if (tx >= l && tx <= r && ty >= 1 && ty <= m && dy != 1) {
      if (a[tx][ty] > a[x][y]) mx = std::max(mx, a[tx][ty]);
      if (a[tx][ty] < a[x][y]) _mx = std::max(_mx, a[tx][ty]);
    }
  }
  if (!mx) mx = kInf;
  else mx = a[x][y];
  return mx - _mx;
}

void dickdreamer() {
  std::cin >> n >> m;
  init(a);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      std::cin >> a[i][j];
  if (n > m) work();
  init(val1), init(val2), init(val3);
  discrete();
  int64_t ans = 0;
  for (int l = 1; l <= n; ++l) {
    for (int i = 1; i <= m; ++i) {
      valt1[i] = val1[l][i] = getval1(l, l, l, i);
      valt2[i] = val2[l][i] = getval2(l, l, l, i);
      valt3[i] = val3[l][i] = getval3(l, l, l, i);
    }
    for (int r = l + 1; r <= n; ++r) {
      __gnu_pbds::gp_hash_table<int, int> mp;
      int sum = 0;
      for (int i = 1; i <= m; ++i) {
        val1[r][i] = getval1(l, r, r, i);
        valt1[i] += getval1(l, r, r - 1, i) - val1[r - 1][i] + val1[r][i];
        val2[r][i] = getval2(l, r, r, i);
        valt2[i] += getval2(l, r, r - 1, i) - val2[r - 1][i] + val2[r][i];
        val3[r][i] = getval3(l, r, r, i);
        valt3[i] += getval3(l, r, r - 1, i) - val3[r - 1][i] + val3[r][i];
        if (mp.find(kInf - sum - valt3[i]) != mp.end()) ans += mp[kInf - sum - valt3[i]];
        sum += valt1[i];
        ++mp[valt2[i] - sum];
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    int lst[2] = {-1, -1};
    std::vector<int> vec;
    for (int j = 1; j < m; ++j)
      vec.emplace_back(a[i][j] < a[i][j + 1]);
    ans += m;
    for (int j = 0; j < (int)vec.size(); ++j) {
      if (!vec[j]) {
        ans += j - lst[1];
        lst[0] = j;
      } else {
        ans += j - lst[0];
        lst[1] = j;
      }
    }
  }
  for (int i = 1; i <= m; ++i) {
    int lst[2] = {-1, -1};
    std::vector<int> vec;
    for (int j = 1; j < n; ++j)
      vec.emplace_back(a[j][i] < a[j + 1][i]);
    for (int j = 0; j < (int)vec.size(); ++j) {
      if (!vec[j]) {
        ans += j - lst[1];
        lst[0] = j;
      } else {
        ans += j - lst[0];
        lst[1] = j;
      }
    }
  }
  std::cout << ans << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}