传送门1
传送门2 题目描述
Little Sultan has a new chess set. But he finds it more amusing to make some new variants of his own than the original game of chess. Here he challenges you with one of his new variants. On a n × n chessboard m bishops are placed. You have to calculate how many square cells of the chessboard are not attacked by any of those bishops.
Input
On the first line you will be given L which denotes the number of input sets you have to process. For each of the input sets, you will have the following: n, m on a line. Each of the following m lines will have two integers: r i and c i denoting the row and column position of the bishops (1-based). Constraints:
1 ≤ n ≤ 400000 ≤ m ≤ 10000The positions for the bishops will be distinct.1 ≤ r i, c i ≤ nOutput For each input set, output the set number as the sample output suggests and the number of cells which are not attacked by any of the bishops.
样例输入
2 1 1 1 1 2 1 2 1Sample Output
Case #1: 0 Case #2: 2翻译：
在一个n×n的棋盘上放了m个象，象可以攻击其所在对角线上的所有格子。求有多少个格子没有被象攻击到。
数据范围： 1 ≤ n ≤ 4 × 1 0 4 1\leq n \leq 4\times 10^4 1≤n≤4×104， 0 < m ≤ 1 0 4 0 <m\leq 10^4 0<m≤104
我们可以把这个 n × n n\times n n×n的棋盘看成下图 则划出来的对角线一共有 2 × n − 1 2 \times n - 1 2×n−1条. 因为中间的那条对角线算了两边，所以一共只有 2 × n − 1 2\times n-1 2×n−1条对角线。
最后我们可以这样做： bool flag[2 * n - 1]表示第 i i i条/的对角线有没有点。 bool flag2[ ]表示如果在包含(i, j)这一条\的对角线有没点。 int sum[ ]的作用是求一次部分和，然后算出答案。
