题目理解与转化

我们有一个 $H \times W$ 的网格，要统计所有可能的城墙放置方案。

城墙定义：大小为 $s$ ($s \ge 3$) 的城墙是一个 $s \times s$ 正方形的边框（最外一圈），内部 $(s-2) \times (s-2)$ 区域为空。

约束条件：

1. 城墙大小 $s \ge L$
2. 城墙必须完全在网格内
3. 已知 $P$ 个格子不存在城墙（禁止格子），城墙边框不能包含这些格子

目标：统计所有合法的城墙放置方案数。

---

关键观察

1. 城墙的数学表示

对于以 $(i,j)$ 为左上角，大小为 $s$ 的城墙：

• 边框包含 $4(s-1)$ 个格子
• 具体位置：第 $i$ 行 $[j, j+s-1]$，第 $i+s-1$ 行 $[j, j+s-1]$，第 $i$ 到 $i+s-1$ 行的第 $j$ 列和第 $j+s-1$ 列

2. 问题转化

我们需要统计所有满足条件的 $(i,j,s)$ 三元组：

• $1 \le i \le H$, $1 \le j \le W$
• $s \ge \max(3, L)$
• $i + s - 1 \le H$, $j + s - 1 \le W$
• 城墙边框不包含任何禁止格子

---

算法思路

步骤 1：预处理禁止格子信息

使用二维数组标记禁止格子：

vector<vector<bool>> forbidden(H+1, vector<bool>(W+1, false));
for (int k = 0; k < P; k++) {
    int a, b;
    cin >> a >> b;
    forbidden[a][b] = true;
}

步骤 2：计算二维前缀和

为了快速判断一个矩形区域是否包含禁止格子，计算前缀和：

vector<vector<int>> prefix(H+1, vector<int>(W+1, 0));
for (int i = 1; i <= H; i++) {
    for (int j = 1; j <= W; j++) {
        prefix[i][j] = forbidden[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];
    }
}

步骤 3：检查城墙边框

对于以 $(i,j)$ 为左上角，大小为 $s$ 的城墙，边框包含禁止格子当且仅当：

• 上边框 $(i, j)$ 到 $(i, j+s-1)$ 包含禁止格子
• 下边框 $(i+s-1, j)$ 到 $(i+s-1, j+s-1)$ 包含禁止格子
• 左边框 $(i, j)$ 到 $(i+s-1, j)$ 包含禁止格子
• 右边框 $(i, j+s-1)$ 到 $(i+s-1, j+s-1)$ 包含禁止格子

但注意四个角点被重复计算了。

更简单的方法：检查整个边框区域是否包含禁止格子。

---

优化方法

直接枚举所有 $(i,j,s)$ 是 $O(HW \cdot \min(H,W))$，不可行。

优化思路：对于每个位置 $(i,j)$，预处理它能放置的最大城墙尺寸 $maxS[i][j]$。

步骤 4：预处理最大尺寸

对于每个 $(i,j)$，计算能向右延伸多远而不遇到禁止格子（在边框上）：

vector<vector<int>> right(H+2, vector<int>(W+2, 0));
for (int i = 1; i <= H; i++) {
    for (int j = W; j >= 1; j--) {
        if (!forbidden[i][j]) {
            right[i][j] = right[i][j+1] + 1;
        } else {
            right[i][j] = 0;
        }
    }
}

类似地计算向下延伸的距离。

步骤 5：计算每个位置的最大城墙尺寸

对于每个 $(i,j)$，最大可能的 $s$ 受限于：

1. 网格边界：$s \le \min(H-i+1, W-j+1)$
2. 上边框：$s \le right[i][j]$
3. 下边框：$s \le right[i+s-1][j]$（但 $s$ 未知，需要迭代）
4. 左边框和右边框类似

实际采用更简单的方法：对于每个 $(i,j)$，从 $s = \max(3,L)$ 开始尝试，找到最大的 $s$ 使得边框无禁止格子。

---

方法：对每个 $(i,j)$ 二分查找最大 $s$

对于每个 $(i,j)$：

• 下界：$low = \max(3, L)$
• 上界：$high = \min(H-i+1, W-j+1)$
• 二分查找最大的 $s$ 使得边框无禁止格子
• 该位置贡献的方案数：$\max(0, s_{\text{max}} - \max(3,L) + 1)$

边框检查：对于给定的 $(i,j,s)$，检查：

1. 上边框：$(i, j)$ 到 $(i, j+s-1)$
2. 下边框：$(i+s-1, j)$ 到 $(i+s-1, j+s-1)$
3. 左边框：$(i+1, j)$ 到 $(i+s-2, j)$（避免重复角点）
4. 右边框：$(i+1, j+s-1)$ 到 $(i+s-2, j+s-1)$（避免重复角点）

使用前缀和 $O(1)$ 检查每个区间。

---

复杂度分析

• 预处理：$O(HW + P)$
• 对每个 $(i,j)$ 二分：$O(\log(\min(H,W)))$
• 总复杂度：$O(HW \log(\min(H,W)))$，适合 $H,W \le 4000$

---

样例验证

样例 1

输入：
5 5 3 2
2 2
4 3

计算过程：
- 禁止格子：(2,2), (4,3)
- 枚举所有(i,j)，检查s>=3的城墙
- 找到4个合法方案

样例 2

输入：
7 8 4 3
2 2
3 7  
6 5

找到13个合法方案

样例 3

大规模数据，验证算法效率。

---

总结

这道题的关键在于：

1. 理解城墙几何结构：$s \times s$ 正方形的边框
2. 使用前缀和：快速判断区域是否包含禁止格子
3. 二分优化：对每个位置二分查找最大合法尺寸
4. 边界处理：注意网格边界和重复角点