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

输入 #1

2 3 1
2 3

输出 #1

6

输入输出样例 #2

输入 #2

3 2 6
1 1
1 2
2 1
2 2
3 1
3 2

输出 #2

0

输入输出样例 #3

输入 #3

1 1 0

输出 #3

1

输入输出样例 #4

输入 #4

3000 3000 0

输出 #4

9004500500

说明/提示

限制条件

• $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 翻译