题解

题意重述：给定一个 $R\times C$ 的棋盘，初始有 $N$ 个格子有草。每年选择一个统一的风向（上/下/左/右），当年夏天所有已有草同时产生种子并被风向平移一格，来年这些落点长出新草，旧草不枯萎。等价于：设初始点集为 $S$，则风向序列的一条曼哈顿路径的每个前缀位移 $v_0=0, v_1, \dots, v_t$，把 $S$ 的平移 $S+v_i$ 依次“盖在”棋盘上，答案是使得并集覆盖整个矩形所需的最短步数 $t$。

核心观察：棋盘中任何一块“没有初始草”的轴对齐矩形（称为空矩形），要被覆盖必须从 $x$ 方向或 $y$ 方向“推进”足够的步数。

• 若空矩形在 $x$ 方向跨满整高（$xl=1$ 且 $xr=R$），则仅能靠 $y$ 方向推进覆盖：如果它贴左边界，只需向右推进至少 $leny$；贴右边界，只需向左推进至少 $leny$；若内部，则左右推进之和至少 $leny$。
• 若空矩形在 $y$ 方向跨满整宽（$yl=1$ 且 $yr=C$），同理仅能靠 $x$ 方向推进覆盖：贴上（或下）时单侧推进至少 $lenx$；内部则上下推进之和至少 $lenx$。
• 对既不跨满 $x$ 也不跨满 $y$ 的空矩形，既可以用 $x$ 方向的推进“跨过”它的高度，也可以把尚未被 $x$ 解决的部分留给 $y$ 方向去满足其宽度需求。由此可把每个矩形转化为对 $x/y$ 推进步数的下界（或和的下界）约束。

枚举最大空矩形（不重不漏）：

• 采用按最小 $x$ 分治 + 按 $y$ 划分的方式（类似二维的笛卡尔树/递归划分）。在函数 solve(l,r,vc,las) 中，vc 是区间 $[l,r]$ 内的候选点集合，取其中 $x$ 最小的点 mn，以 sy[mn] 将集合按 $y$ 分为上下两半递归。递归过程中，凡是当前最小 $x$ 与上层边界之间存在空行段，或在某侧 $y$ 区间内没有点，即得到一块最大空矩形 $(xl..xr,\,yl..yr)$，交给 opt 归并。
• opt 根据矩形是否贴到四边判定其类型：$x$ 方向三类（贴上、贴下、内部），$y$ 方向三类（贴左、贴右、内部）。
  • 若矩形跨满 x，则把对 y 的硬下界并入 Y[jy]。
  • 若矩形跨满 y，则把对 x 的硬下界并入 X[jx]。
  • 其他情形记录为三元组 (lenx,leny,jy) 加入桶 S[jx]，表示“若用 $x$ 推进不足 $lenx$，则必须用 $y$ 满足对应 jy 的需求 $leny$”。

合并约束并最小化答案：

• 对三类 $jx\in\{0,1,2\}$（分别对应贴上、贴下、内部）的集合 $S[jx]$ 按 $lenx$ 升序排序。三重线性扫枚举每类一个阈值区间，使得“$lenx$ 不超过阈值”的矩形视为已由 $x$ 方向解决；其余矩形必须把 $leny$ 并入对应的下界。内部类还要维护“上下推进之和 $\ge lenx$”的额外约束，因此第三层循环维护可行区间并与前两类的和约束联动剪枝。
• 在任一阈值组合下：
  • $y$ 方向最少步数为 $\max\!\big( Y_{left}+Y_{right},\; Y_{inside} \big)$（两侧之和与内部约束取较大）。
  • $x$ 方向最少步数为 $\max\!\big( X_{top}+X_{bottom},\; X_{inside} \big)$（同理）。 代码中对应 res = min(res, max(Yk[0]+Yk[1], Yk[2]) + max(l0+l1, l2))。

复杂度与实现要点：

• 递归划分产生的最大空矩形数量在本题范围内可控；三重“阈值”扫描每层均为线性游标推进，整体时间复杂度近似 $O(N^2)$，空间 $O(N)$。
• judgex/judgey 判断矩形与边界关系；X,Y 记录跨满另一维时的硬下界；对 S[jx] 排序并设 INF 哨兵便于滑动窗口。
• $R, C$ 可达 $10^9$，仅作为边长参与计算；读入采用自定义快读。

#include <array>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int read() {
    char c = getchar();
    int x = 0;

    while (c < 48 || c > 57)
        c = getchar();

    do
        x = x * 10 + (c ^ 48), c = getchar();

    while (c >= 48 && c <= 57);

    return x;
}
typedef long long ll;
const int N = 303, T = 200003;
const ll INF = 0x3f3f3f3f3f3f3f3f;
typedef array<ll, 3> arr;
typedef vector<int> vi;
int R, C, n, cur;
ll res = INF;
int sx[N], sy[N];
arr X, Y;
inline void chmx(ll &x, ll v) {
    if (x < v)
        x = v;
}
inline void chmn(ll &x, ll v) {
    if (x > v)
        x = v;
}
struct node {
    ll u, v;
    int d;
    friend bool operator<(const node a, const node b) {
        return a.u < b.u;
    }
} S[3][T];
arr W;
inline int judgex(int xl, int xr) {
    if (xl == 1 && xr == R)
        return -1;

    if (xl == 1)
        return 0;

    if (xr == R)
        return 1;

    return 2;
}
inline int judgey(int yl, int yr) {
    if (yl == 1 && yr == C)
        return -1;

    if (yl == 1)
        return 0;

    if (yr == C)
        return 1;

    return 2;
}
void opt(int xl, int xr, int yl, int yr) {
    int lenx = xr - xl + 1, leny = yr - yl + 1;
    int jx = judgex(xl, xr), jy = judgey(yl, yr);

    if (jx < 0)
        return chmx(Y[jy], leny);

    if (jy < 0)
        return chmx(X[jx], lenx);

    S[jx][W[jx]++] = (node) {
        lenx, leny, jy
    };
}
void solve(int l, int r, vi vc, int las) {
    if (vc.empty())
        return opt(sx[cur] + 1, R, l, r);

    int mn = vc.front();

    for (int x : vc)
        if (sx[x] < sx[mn])
            mn = x;

    if (sx[cur] < sx[mn] - 1 && sx[mn] > las)
        opt(sx[cur] + 1, sx[mn] - 1, l, r);

    if ((!cur || sy[cur] < sy[mn]) && l < sy[mn]) {
        vi tmp;

        for (int x : vc)
            if (sy[x] < sy[mn])
                tmp.emplace_back(x);

        solve(l, sy[mn] - 1, tmp, sx[mn]);
    }

    if ((!cur || sy[cur] > sy[mn]) && sy[mn] < r) {
        vi tmp;

        for (int x : vc)
            if (sy[x] > sy[mn])
                tmp.emplace_back(x);

        solve(sy[mn] + 1, r, tmp, sx[mn]);
    }
}
signed main() {
    R = read();
    C = read();
    n = read();

    for (int i = 1; i <= n; ++i)
        sx[i] = read(), sy[i] = read();

    vi init;

    for (int i = 1; i <= n; ++i) {
        if (sx[i] == R)
            continue;

        for (int j = 1; j <= n; ++j)
            if (sx[j] > sx[i])
                init.emplace_back(j);

        cur = i;
        solve(1, C, init, 0);
        init.clear();
    }

    for (int i = 1; i <= n; ++i)
        init.emplace_back(i);

    cur = 0;
    solve(1, C, init, 0);

    for (int t = 0; t < 3; ++t)
        sort(S[t], S[t] + W[t]), S[t][W[t]].u = INF;

    arr Yi = Y;

    for (int i = W[0]; ~i; --i) {
        if (i < W[0])
            chmx(Yi[S[0][i].d], S[0][i].v);

        ll l0 = X[0], r0 = S[0][i].u - 1;

        if (l0 > r0)
            break;

        if (i)
            chmx(l0, S[0][i - 1].u);

        if (l0 > r0)
            continue;

        arr Yj = Yi;

        for (int j = W[1]; ~j; --j) {
            if (j < W[1])
                chmx(Yj[S[1][j].d], S[1][j].v);

            ll l1 = X[1], r1 = S[1][j].u - 1;

            if (l1 > r1)
                break;

            if (j)
                chmx(l1, S[1][j - 1].u);

            if (l1 > r1)
                continue;

            arr Yk = Yj;

            for (int k = W[2]; ~k; --k) {
                if (k < W[2])
                    chmx(Yk[S[2][k].d], S[2][k].v);

                if (k && S[2][k - 1].u == S[2][k].u)
                    continue;

                ll l2 = X[2], r2 = S[2][k].u - 1;

                if (l2 > r2)
                    break;

                if (k)
                    chmx(l2, S[2][k - 1].u);

                if (l2 > r2 || l2 > r0 + r1)
                    continue;

                if (r2 < l0 + l1)
                    break;

                chmn(res, max(Yk[0] + Yk[1], Yk[2]) + max(l0 + l1, l2));
            }
        }
    }

    printf("%lld\n", res);
    return 0;
}