AT_abc377_c [ABC377C] Avoid Knight Attack

题目描述

有一个由 $N$ 行 $N$ 列组成的 $N^2$ 个格子的棋盘。我们将从上往下第 $i$ 行（$1\leq i\leq N$）、从左往右第 $j$ 列（$1\leq j\leq N$）的格子称为格子 $(i,j)$。

每个格子要么是空格，要么已经放置了一个棋子。棋盘上总共放置了 $M$ 个棋子，第 $k$ 个棋子（$1\leq k\leq M$）放在格子 $(a_k, b_k)$ 上。

你想要在任意一个空格上放置你自己的棋子，并且要保证不会被已经放置的任意一个棋子吃掉。

放在格子 $(i,j)$ 上的棋子可以吃掉满足下列任意一个条件的棋子：

• 放在 $(i+2, j+1)$ 上
• 放在 $(i+1, j+2)$ 上
• 放在 $(i-1, j+2)$ 上
• 放在 $(i-2, j+1)$ 上
• 放在 $(i-2, j-1)$ 上
• 放在 $(i-1, j-2)$ 上
• 放在 $(i+1, j-2)$ 上
• 放在 $(i+2, j-1)$ 上

但对于不存在的格子，这些条件始终不成立。

例如，放在格子 $(4,4)$ 上的棋子可以吃掉下图中蓝色格子上的棋子。

请你计算，有多少个格子可以放置你的棋子，并且不会被已经放置的棋子吃掉。

输入格式

输入按以下格式从标准输入读入。

$N$ $M$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_M$ $b_M$

输出格式

输出一个整数，表示可以放置你的棋子且不会被已有棋子吃掉的空格的数量。

输入输出样例 #1

输入 #1

8 6
1 4
2 1
3 8
4 5
5 2
8 3

输出 #1

38

输入输出样例 #2

输入 #2

1000000000 1
1 1

输出 #2

999999999999999997

输入输出样例 #3

输入 #3

20 10
1 4
7 11
7 15
8 10
11 6
12 5
13 1
15 2
20 10
20 15

输出 #3

338

说明/提示

限制条件

• $1\leq N\leq 10^9$
• $1\leq M\leq 2\times 10^5$
• $1\leq a_k\leq N, 1\leq b_k\leq N\ (1\leq k\leq M)$
• $(a_k, b_k)\neq(a_l, b_l)\ (1\leq k<l\leq M)$
• 输入均为整数

样例解释 1

已经放置的棋子可以吃掉下图中蓝色格子上的棋子。

因此，剩下 $38$ 个格子可以放置你的棋子且不会被已有棋子吃掉。

样例解释 2

$10^{18}$ 个格子中，不能放置的格子只有 $(1,1),(2,3),(3,2)$ 这 $3$ 个格子。
请注意，答案可能大于 $2^{32}$。

由 ChatGPT 4.1 翻译