正睿 2023 noip 10 连 Day7 T3

Description

给定一个 $n\times m$ 的网格以及 $q$ 个矩形。记第 $x$ 行第 $y$ 列的格子为 $(x,y)$。

考虑一个 $n\times m$ 的有向无环图，点 $(x_1,y_1)$ 向 $(x_2,y_2)$ 有连边当且仅当 $x_1<x_2,y_1<y_2$ 且存在一个矩形同时包含 $(x_1,y_1)$ 与 $(x_2,y_2)$。定义矩形 $(x_1,y_1,x_2,y_2)$ 包含了所有 $x\in [x_1,x_2],y\in [y_1,y_2]$ 的 $(x,y)$。

定义路径长度为路径包含的节点个数。请求出该图中的最长路径，以及长度最长的路径共有多少条。路径条数对 $10^9 + 7$ 取模。

保证 $1\leq T \leq 10^5,1\leq \sum nm \leq 1.2 \times 10^7,1\leq \sum q \leq 5\times 10^5$。

Solution

设 $f_{i,j}$ 表示结尾为 $(i,j)$ 的最长路径长度，$g_{i,j}$ 表示 $(i,j)$ 最长路径的方案数。

容易发现 $(i,j)$ 的上一步一定是 $(i-1,?)$ 或者 $(?,j-1)$。

因为如果上一步的 $(x,y)$ 满足 $x\leq i-2,y\leq j-2$ 的话，他们中间一定还可以加点，就不是最优的了。

然后考虑 $f_{i-1,x}$ 的转移。容易发现 $x$ 的取值一定是一段以 $j-1$ 结尾的区间。

不妨设区间为 $[lx_{i,j},j-1]$。

容易发现 $lx_{i,j}$ 单调不减，所以可以单调队列优化 dp。

---

然后思考怎么求出 $lx_{i,j}$。

对于一个矩形 $(x_1,y_1,x_2,y_2)$ 对 $lx$ 造成的影响就是对 $(x_1+1,y_1,x_2,y_2)$ 这个矩形的 $lx$ 与 $y_1$ 取 min。

容易发现这个等价于对 $(x_1+1,1,x_2,y_2)$ 取 min。

于是对于每个 $y$ 维护一个吉司机线段树，然后对所有的 $x$ 取后缀 min 即可。

时间复杂度：$O(nm+q\log n)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

using i64 = int64_t;

namespace FASTIO {
char ibuf[1 << 21], *p1 = ibuf, *p2 = ibuf;
char getc() {
  return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template<class T> bool read(T &x) {
  x = 0; int f = 0; char ch = getc();
  while (ch < '0' || ch > '9') f |= ch == '-', ch = getc();
  while (ch >= '0' && ch <= '9') x = (x * 10) + (ch ^ 48), ch = getc();
  x = (f ? -x : x); return 1;
}
template<typename A, typename ...B> bool read(A &x, B &...y) { return read(x) && read(y...); }
} // namespace FASTIO
using FASTIO::read;

const int kMaxN = 2e3 + 5, kMod = 1e9 + 7;

int n, m, q;
int f[kMaxN][kMaxN], g[kMaxN][kMaxN], lx[kMaxN][kMaxN], ly[kMaxN][kMaxN];
int qx[kMaxN][kMaxN], qy[kMaxN][kMaxN], hx[kMaxN], tx[kMaxN], hy[kMaxN], ty[kMaxN];
int cntx[kMaxN][kMaxN], cnty[kMaxN][kMaxN];

struct SGT {
  int mxx, mx[kMaxN << 2], se[kMaxN << 2], tag[kMaxN << 2], idx[kMaxN];
  bool have[kMaxN << 2];

  void pushup(int x) {
    if (mx[x << 1] == mx[x << 1 | 1]) {
      mx[x] = mx[x << 1], se[x] = std::max(se[x << 1], se[x << 1 | 1]);
    } else if (mx[x << 1] > mx[x << 1 | 1]) {
      mx[x] = mx[x << 1], se[x] = std::max(se[x << 1], mx[x << 1 | 1]);
    } else {
      mx[x] = mx[x << 1 | 1], se[x] = std::max(mx[x << 1], se[x << 1 | 1]);
    }
  }

  void addtag(int x, int v) {
    if (mx[x] <= v) return;
    mx[x] = tag[x] = v;
  }

  void pushdown(int x) {
    if (!~tag[x]) return;
    addtag(x << 1, tag[x]), addtag(x << 1 | 1, tag[x]);
    tag[x] = -1;
  }

  void build(int x, int l, int r) {
    mx[x] = 1e9, se[x] = 0, tag[x] = -1, mxx = std::max(mxx, x);
    have[x] = (l != r);
    if (l == r) {
      idx[l] = x;
      return;
    }
    int mid = (l + r) >> 1;
    build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
    pushup(x);
  }

  void update(int x, int l, int r, int ql, int qr, int v) {
    if (l > qr || r < ql) {
      return;
    } else if (l >= ql && r <= qr) {
      if (v >= mx[x]) return;
      else if (v > se[x]) return addtag(x, v);
    }
    pushdown(x);
    int mid = (l + r) >> 1;
    update(x << 1, l, mid, ql, qr, v), update(x << 1 | 1, mid + 1, r, ql, qr, v);
    pushup(x);
  }

  void pushall() {
    for (int i = 1; i <= mxx; ++i)
      if (have[i])
        pushdown(i);
    for (int i = mxx; i; --i)
      if (have[i])
        pushup(i);
  }

  int query(int x) { return mx[idx[x]]; }
} sx[kMaxN], sy[kMaxN];

void inc(int &x, int y) { (x += y) >= kMod ? (x -= kMod) : x; }
void dec(int &x, int y) { (x -= y) < 0 ? (x += kMod) : x; }

void solve() {
  for (int i = 0; i <= n; ++i) {
    hx[i] = 1, tx[i] = 0;
    std::fill_n(cntx[i], std::max(n, m) + 1, 0);
  }
  for (int i = 0; i <= m; ++i) {
    hy[i] = 1, ty[i] = 0;
    std::fill_n(cnty[i], std::max(n, m) + 1, 0);
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (i > 1) { // qx
        if (j > 1) {
          for (; hx[i - 1] <= tx[i - 1] && f[i - 1][qx[i - 1][tx[i - 1]]] < f[i - 1][j - 1]; --tx[i - 1]) {
            dec(cntx[i - 1][f[i - 1][qx[i - 1][tx[i - 1]]]], g[i - 1][qx[i - 1][tx[i - 1]]]);
          }
          qx[i - 1][++tx[i - 1]] = j - 1;
          inc(cntx[i - 1][f[i - 1][j - 1]], g[i - 1][j - 1]);
        }
        for (; hx[i - 1] <= tx[i - 1] && qx[i - 1][hx[i - 1]] < lx[i][j]; ++hx[i - 1]) {
          dec(cntx[i - 1][f[i - 1][qx[i - 1][hx[i - 1]]]], g[i - 1][qx[i - 1][hx[i - 1]]]);
        }
        if (hx[i - 1] <= tx[i - 1]) {
          int mx = f[i - 1][qx[i - 1][hx[i - 1]]] + 1, cnt = cntx[i - 1][mx - 1];
          if (mx > f[i][j]) {
            f[i][j] = mx, g[i][j] = cnt;
          } else if (mx == f[i][j]) {
            inc(g[i][j], cnt);
          }
        }
      }
      if (j > 1) { // qy
        if (i > 2) {
          for (; hy[j - 1] <= ty[j - 1] && f[qy[j - 1][ty[j - 1]]][j - 1] < f[i - 2][j - 1]; --ty[j - 1]) {
            dec(cnty[j - 1][f[qy[j - 1][ty[j - 1]]][j - 1]], g[qy[j - 1][ty[j - 1]]][j - 1]);
          }
          qy[j - 1][++ty[j - 1]] = i - 2;
          inc(cnty[j - 1][f[i - 2][j - 1]], g[i - 2][j - 1]);
        }
        for (; hy[j - 1] <= ty[j - 1] && qy[j - 1][hy[j - 1]] < ly[i][j]; ++hy[j - 1]) {
          dec(cnty[j - 1][f[qy[j - 1][hy[j - 1]]][j - 1]], g[qy[j - 1][hy[j - 1]]][j - 1]);
        }
        if (hy[j - 1] <= ty[j - 1]) {
          int mx = f[qy[j - 1][hy[j - 1]]][j - 1] + 1, cnt = cnty[j - 1][mx - 1];
          if (mx > f[i][j]) {
            f[i][j] = mx, g[i][j] = cnt;
          } else if (mx == f[i][j]) {
            inc(g[i][j], cnt);
          }
        }
      }
    }
  }
}

void dickdreamer() {
  read(n, m, q);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      f[i][j] = g[i][j] = 1;
      lx[i][j] = ly[i][j] = 1e9;
    }
  }
  for (int i = 1; i <= m; ++i)
    sx[i].mxx = 0, sx[i].build(1, 1, n);
  for (int i = 1; i <= n; ++i)
    sy[i].mxx = 0, sy[i].build(1, 1, m);
  for (int cs = 1; cs <= q; ++cs) {
    int _x1, _y1, _x2, _y2;
    read(_x1, _y1, _x2, _y2);
    if (_x1 < _x2) sx[_y2].update(1, 1, n, _x1 + 1, _x2, _y1);
    if (_y1 < _y2) sy[_x2].update(1, 1, m, _y1 + 1, _y2, _x1);
  }
  for (int i = m; i; --i) {
    sx[i].pushall();
    for (int j = 1; j <= n; ++j) {
      lx[j][i] = sx[i].query(j);
      if (i != m) lx[j][i] = std::min(lx[j][i], lx[j][i + 1]);
    }
  }
  for (int i = n; i; --i) {
    sy[i].pushall();
    for (int j = 1; j <= m; ++j) {
      ly[i][j] = sy[i].query(j);
      if (i != n) ly[i][j] = std::min(ly[i][j], ly[i + 1][j]);
    }
  }
  solve();
  int mx = 0, cnt = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (f[i][j] > mx) {
        mx = f[i][j], cnt = g[i][j];
      } else if (f[i][j] == mx) {
        cnt = (cnt + g[i][j]) % kMod;
      }
    }
  }
  std::cout << mx << ' ' << cnt << '\n';
}

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