AT_abc377_f [ABC377F] Avoid Queen 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$ 行上的棋子
• 在第 $j$ 列上的棋子
• 在满足 $i+j=a+b$ 的格子 $(a,b)$ 上的棋子（即主对角线方向）
• 在满足 $i-j=a-b$ 的格子 $(a,b)$ 上的棋子（即副对角线方向）

例如，放在格子 $(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

2

输入输出样例 #2

输入 #2

1000000000 1
1 1

输出 #2

999999997000000002

输入输出样例 #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

77

说明/提示

限制条件

• $1\leq N\leq 10^9$
• $1\leq M\leq 10^3$
• $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

已经放置的棋子可以吃掉下图中蓝色标记的格子上的棋子。
因此，你可以安全放置棋子的格子是 $(6,6)$ 和 $(7,7)$，共 $2$ 个。

样例解释 2

在 $10^{18}$ 个格子中，不能放置的格子为第 $1$ 行、第 $1$ 列，以及 $(1,1),(2,2),\ldots,(10^9,10^9)$ 共 $3\times 10^9-2$ 个格子。注意答案可能大于 $2^{32}$。

由 ChatGPT 4.1 翻译