103114: [Atcoder]ABC311 E - Defect-free Squares

Problem Statement

There is a grid with $H$ rows and $W$ columns. Let $(i, j)$ denote the square at the $i$-th row from the top and $j$-th column from the left of the grid.
Each square of the grid is holed or not. There are exactly $N$ holed squares: $(a_1, b_1), (a_2, b_2), \dots, (a_N, b_N)$.

When the triple of positive integers satisfies the following condition, the square region whose top-left corner is $(i, j)$ and whose bottom-right corner is $(i + n - 1, j + n - 1)$ is called a holeless square.

• $i + n - 1 \leq H$.
• $j + n - 1 \leq W$.
• For every pair of non-negative integers $(k, l)$ such that $0 \leq k \leq n - 1, 0 \leq l \leq n - 1$, square $(i + k, j + l)$ is not holed.

How many holeless squares are in the grid?

Constraints

• $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$
• All $(a_i, b_i)$ are pairwise different.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$H$ $W$ $N$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_N$ $b_N$

Output

Print the number of holeless squares.

Sample Input 1

2 3 1
2 3

Sample Output 1

6

There are six holeless squares, listed below. For the first five, $n = 1$, and the top-left and bottom-right corners are the same square.

• The square region whose top-left and bottom-right corners are $(1, 1)$.
• The square region whose top-left and bottom-right corners are $(1, 2)$.
• The square region whose top-left and bottom-right corners are $(1, 3)$.
• The square region whose top-left and bottom-right corners are $(2, 1)$.
• The square region whose top-left and bottom-right corners are $(2, 2)$.
• The square region whose top-left corner is $(1, 1)$ and whose bottom-right corner is $(2, 2)$.

Sample Input 2

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

Sample Output 2

0

There may be no holeless square.

Sample Input 3

1 1 0

Sample Output 3

1

The whole grid may be a holeless square.

Sample Input 4

3000 3000 0

Sample Output 4

9004500500

问题描述

有一个包含$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$。
• 对于每一对非负整数$(k, l)$，满足$0 \leq k \leq n - 1, 0 \leq l \leq n - 1$，方格$(i + k, j + l)$没有洞。

网格中有多少个无洞的正方形？

约束条件

• $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)$两两不同。
• 所有的输入值都是整数。

输入

输入从标准输入按照以下格式给出：

$H$ $W$ $N$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_N$ $b_N$

输出

打印无洞的正方形的数量。

样例输入1

2 3 1
2 3

样例输出1

6

有六个无洞的正方形，如下所示。前五个的$n=1$，左上角和右下角是同一个方格。

• 其左上角和右下角为$(1, 1)$的正方形区域。
• 其左上角和右下角为$(1, 2)$的正方形区域。
• 其左上角和右下角为$(1, 3)$的正方形区域。
• 其左上角和右下角为$(2, 1)$的正方形区域。
• 其左上角和右下角为$(2, 2)$的正方形区域。
• 其左上角为$(1, 1)$，右下角为$(2, 2)$的正方形区域。

样例输入2

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

样例输出2

0

可能没有无洞的正方形。

样例输入3

1 1 0

样例输出3

1

整个网格可能是一个无洞的正方形。

样例输入4

3000 3000 0

样例输出4

9004500500