AT_abc311_e [ABC311E] Defect-free Squares

有一个高为 $H$ 行、宽为 $W$ 列的网格。网格中从上往下第 $i$ 行、从左往右第 $j$ 列的格子记作 $(i, j)$。 网格中的每个格子要么有洞，要么没有洞。恰好有 $N$ 个格子有洞，这些格子的位置分别为 $(a_1, b_1), (a_2, b_2), \dots, (a_N, b_N)$。 当正整数三元组 $(i, j, n)$ 满足以下条件时，以 $(i, j)$ 为左上角、$(i + n - 1, j + n - 1)$ 为右下角的正方形区域被称为**没有洞的正方形**： - $i + n - 1 \leq H$ - $j + n - 1 \leq W$ - 对于所有满足 $0 \leq k \leq n - 1, 0 \leq l \leq n - 1$ 的非负整数对 $(k, l)$，$(i + k, j + l)$ 这个格子没有洞。 请问网格中一共有多少个没有洞的正方形？

输入按以下格式从标准输入读入。 > $H$ $W$ $N$ > $a_1$ $b_1$ > $a_2$ $b_2$ > $\vdots$ > $a_N$ $b_N$

输出没有洞的正方形的个数。

## 限制条件 - $1 \leq H, W \leq 3000$ - $0 \leq N \leq \min(H \times W, 10^5)$ - $1 \leq a_i \leq H$ - $1 \leq b_i \leq W$ - $(a_i, b_i)$ 互不相同 - 输入的所有值均为整数 ## 样例解释 1 没有洞的正方形一共有 $6$ 个。它们分别如下。前 $5$ 个是 $n = 1$ 的情况，即左上角和右下角是同一个格子。 - 以 $(1, 1)$ 为左上角且右下角的正方形区域 - 以 $(1, 2)$ 为左上角且右下角的正方形区域 - 以 $(1, 3)$ 为左上角且右下角的正方形区域 - 以 $(2, 1)$ 为左上角且右下角的正方形区域 - 以 $(2, 2)$ 为左上角且右下角的正方形区域 - 以 $(1, 1)$ 为左上角，$(2, 2)$ 为右下角的正方形区域 ## 样例解释 2 也有可能没有任何没有洞的正方形。 ## 样例解释 3 也有可能存在没有洞的正方形与整个网格重合的情况。 由 ChatGPT 4.1 翻译