题目概述

Bajtazar 想购买一块矩形土地，他的预算范围是 $[k, 2k]$。土地是一个 $n \times n$ 的网格，每个格子有特定的价格。需要找到一块矩形区域，其总价格在预算范围内，或者判断不存在这样的区域。

---

问题分析

关键约束

• 土地必须是矩形
• 总价格 $c$ 满足 $k \leq c \leq 2k$
• $n \leq 2000$，但 $k$ 和价格可以很大（$10^9$ 级别）

特殊情况

1. 单个格子：如果某个格子的价格就在 $[k, 2k]$ 范围内，直接选择这个格子
2. 大矩形：如果整个矩形的价格超过 $2k$，需要寻找子矩形

核心难点

• 暴力枚举所有矩形是 $O(n^4)$，不可行
• 需要高效算法在 $O(n^2)$ 或 $O(n^3)$ 内解决

---

算法思路

总体策略

1. 预处理：计算二维前缀和，快速查询任意矩形区域的和
2. 特殊情况检查：先检查是否有单个格子满足条件
3. 动态规划找候选矩形：使用类似最大全1子矩阵的方法
4. 调整候选矩形：如果候选矩形价格超过 $2k$，尝试缩减它

核心观察

• 如果某个矩形价格 $> 2k$，那么它不可能直接作为答案
• 如果某个矩形价格 $< k$，那么它太小了
• 关键：找到价格 $\geq k$ 且尽量接近 $k$ 的矩形

算法步骤

步骤1：预处理和特殊情况

// 计算二维前缀和
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
        cin >> a[i][j];
        sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + a[i][j];
        // 检查单个格子
        if (a[i][j] >= k && a[i][j] <= 2 * k)
            return cout << j << ' ' << i << ' ' << j << ' ' << i, 0;
    }
}

步骤2：动态规划找候选矩形

对于每一行，维护：

• l[i][j]：从第 i 行第 j 列向左延伸，不遇到 $> 2k$ 的格子的最左边界
• r[i][j]：从第 i 行第 j 列向右延伸，不遇到 $> 2k$ 的格子的最右边界
• up[i][j]：从第 i 行第 j 列向上延伸的高度

这样可以得到以每个位置为右下角的极大矩形。

步骤3：调整候选矩形

如果找到的候选矩形价格 $> 2k$：

• 尝试逐行删除，看是否能进入预算范围
• 对于每行，如果整行价格 $< k$，直接删除
• 如果整行价格在 $[k, 2k]$ 内，直接选择这一行
• 如果整行价格 $> 2k$，尝试在行内找连续区间

---

算法详解

动态规划部分

for (int i = 1; i <= n; ++i) {
    // 计算左右边界
    for (int j = 1; j <= n; ++j) {
        if (a[i][j] > 2 * k) continue;
        l[i & 1][j] = min(j, l[i & 1][j - 1]);
    }
    for (int j = n; j >= 1; --j) {
        if (a[i][j] > 2 * k) continue;
        r[i & 1][j] = max(j, r[i & 1][j + 1]);
    }
    
    // 合并上一行的信息
    for (int j = 1; j <= n; ++j) {
        if (a[i][j] > 2 * k) continue;
        up[i & 1][j] = 1;
        if (i != 1 && a[i - 1][j] < k) {
            l[i & 1][j] = max(l[(i - 1) & 1][j], l[i & 1][j]);
            r[i & 1][j] = min(r[(i - 1) & 1][j], r[i & 1][j]);
            up[i & 1][j] = up[(i - 1) & 1][j] + 1;
        }
        // 记录候选矩形
        upd(i - up[i & 1][j] + 1, l[i & 1][j], i, r[i & 1][j]);
    }
}

调整候选矩形

ll sum = qry(lx, ly, rx, ry);
if (sum < k) {
    cout << "NIE";
} else {
    // 逐行调整
    for (int i = lx; i <= rx; ++i) {
        if (sum <= 2 * k) {
            // 找到满足条件的矩形
            cout << ly << ' ' << i << ' ' << ry << ' ' << rx;
            return 0;
        }
        ll tmp = qry(i, ly, i, ry);  // 当前行的价格
        if (tmp < k) {
            sum -= tmp;  // 删除这一行
        } else if (tmp >= k && tmp <= 2 * k) {
            // 这一行本身就满足条件
            return cout << ly << ' ' << i << ' ' << ry << ' ' << i, 0;
        } else {
            // 在当前行内找连续区间
            ll tot = 0;
            for (int j = ly; j <= ry; ++j) {
                tot += a[i][j];
                if (tot >= k)
                    return cout << ly << ' ' << i << ' ' << j << ' ' << i, 0;
            }
        }
    }
}

---

样例解析

样例1

输入：
4 3
1 1 1
1 9 1
1 1 1
输出：NIE

分析：所有单个格子价格都小于4，所有矩形要么太小（<4），要么太大（>8），没有在[4,8]范围内的。

样例2

输入：
8 4
1 2 1 3
25 1 2 1
4 20 3 3
3 30 12 2
输出：2 1 4 2

分析：算法找到矩形(2,1)到(4,2)，计算其价格在[8,16]范围内。

---

复杂度分析

• 预处理：$O(n^2)$
• 动态规划：$O(n^2)$
• 调整阶段：最坏 $O(n^2)$
• 总复杂度：$O(n^2)$，适合 $n \leq 2000$

---

算法亮点

1. 二维前缀和：快速计算任意矩形区域和
2. 动态规划：高效找到候选矩形
3. 滚动数组：优化空间复杂度
4. 调整策略：当候选矩形过大时的有效缩减方法
5. 特殊情况处理：优先检查单个格子和行内区间

---

总结

这道题的核心在于：

1. 利用约束条件：价格超过 $2k$ 的格子作为障碍
2. 极大矩形算法：类似全1子矩阵的扩展
3. 贪心调整：通过删除行或列来调整矩形大小
4. 完备性：算法能保证找到解或正确判断无解

这种"极大矩形 + 调整优化"的思路在解决带约束的矩形搜索问题时非常有效。