（竞赛题）计算没有被象攻击的方格数量

Question

我的解决方案在下面。

国际象棋中的象是攻击同一条对角线上（两条对角线上）的所有方格的棋子。

Shakhriyar 将 m 个主教放在大小为 n * n 的棋盘上。现在他想数一下没有被主教攻击的方格有多少个。在这件事上帮助 Shahriyar。

输入数据 第一行包含两个整数：棋盘的大小 n (1 ≤ n ≤ 10^6) 和象的数量 m (1 ≤ m ≤ 10^5)。接下来的 m 行中的每一行都包含一对整数： r[i] и c[i] (1 ≤ r[i], c[i] ≤ n) - 主教编号 i 所在的行数和列数。主教编号从 1 到 m。所有主教都位于不同的广场上。

输出数据 打印未被主教攻击的方格数。

https://www.eolymp.com/en/problems/9630

输入示例#1

10 6

4 7

8 5

8 7

6 2

9 7

8 4

输出示例#1

33

我到这里就解决了：

（抱歉图片有点乱）

对角线=2n-1

d-对角线数

(i;j)-点(y,x)的坐标

来自图1：

1:(6;1)

2:(5;1); (6;2)

3:(4;1); (5;2); (6;3)

4:(3;1); (4;2); (5;3); (6;4)

...

10:(1;5); (2;6)

11:(1;6)

d=n-(i-j);

来自图2：

1:(1;1)

2:(1;2); (2;1)

3:(1;3); (3;1); (2;2)

4:(1;4) (4;1) (2;3) (3;2)

...

d=i+j-1;

对角线交点：

图1(2)中的对角线	图2(1)中的对角线
1, 11	6
2, 10	5,6,7
3, 9	4,5,6,7,8
4、8	3,4,5,6,7,8,9
5、7	2,3,4,5,6,7,8,9,10
6	1,2,3,4,5,6,7,8,9,10,11

在求点数时，交叉点阻碍了我。我该如何解决这个问题？

我的代码（C++）：

#include<iostream>
#include<set>
using namespace std;
int main(){
    set<int> hit_diagonals1,hit_diagonals2;
    int n,m;
    cin>>n>>m;
    for(int k=0,i,j; k<m; k++){///O(m)-->1e5
        cin>>i>>j;
        hit_diagonals1.insert(n-(i-j));
        hit_diagonals2.insert(i+j-1);
    }
    int cnt=0;//hit_points_number
    
    //.....
    
    cout<<n*n-cnt<<'\n';
    return 0;
}

Answer 1

您可以使用对角线扫描线算法在 O(m log m) 时间内解决此问题。

首先，我们将 x+y 恒定的对角线称为“反斜杠对角线”，而“斜杠”对角线将是 x-y 恒定的对角线。

现在我们可以按从 0 到 2m+1（最大 x+y）的顺序考虑反斜杠对角线。

首先，列出“事件”。 对于每个主教位置 (x,y)，记录：

• (x+y, 'cover'): 表示主教完全覆盖的反斜杠对角线；
• (abs(x-y), 'enter')：主教开始覆盖其斜线对角线的第一个反斜线对角线：
• (m+m-1-abs(x,y), ' exit')：第一个反斜杠对角线，主教不再覆盖其斜杠对角线。

制作一个最初为空的字典

slashes

来跟踪覆盖每个斜线对角线的主教数量。 在修改此映射时，您还将确保可以跟踪非零条目的数量。

现在，按反斜杠对角线对事件进行排序，并按顺序处理它们，按反斜杠对角线分组。

对于每个反斜杠组 <= (m-1)+(m-1):

• 累计自上次发生事件的反斜杠组以来未受攻击的方块数量。 由于这些反斜杠中没有事件，这意味着您可以使用简单的公式计算未受攻击的方块的数量。
• 处理“进入”和“退出”事件以更新

  slashes

  地图。
• 如果有“覆盖”事件，则直接进入下一组，因为反斜杠中没有未受攻击的方格。
• 否则，使用

  slashes

  中的非零条目数来计算反斜杠中未受攻击的方格数。 它是反斜杠对角线的长度减去非零条目的数量。

最后，如果你没有处理最后一个反斜杠 2(m-1)，那么使用添加所有未处理的反斜杠中的方格数——它们不会受到攻击。

请注意，问题中的约束表明需要 O(m²)、O(m + n) 或 O(m + n log n) 算法。 这是 O(m log m)，这比他们预期的要好。

Answer 2

由于对角线具有小范围内的标识数字，因此您可以使用向量而不是集合。索引为对角线编号，对应的值表示对角线是否受到攻击（0或1）。

算法首先迭代前向对角线（/），只有当发现对角线没有受到攻击时，才迭代相关的交叉对角线来统计同样没有受到攻击的对角线。请注意，交叉对角线的数量取决于所考虑的前对角线，并且这些交叉对角线的数量始终相距 2 步（对于给定的前对角线，它们要么都是奇数，要么都是偶数）。

以下是它的编码方式：

#include <iostream>
#include <vector>

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<int> diagonals(4*n, 1); // initialise with all 1
    
    for (int bishop = 0, row, col; bishop < m; bishop++) {
        std::cin >> row >> col;
        // Mark the two diagonals that this biship covers with 0
        diagonals[row+col] = diagonals[3*n+(row-col)] = 0;
    }
    
    int freeCount = 0;
    for (int forwIdx = 2, lowIdx = 3*n, highIdx = lowIdx; forwIdx <= 2*n; forwIdx++) {
        if (diagonals[forwIdx]) { // Non-attacked diagonal (/)
            // The crossing diagonals (\) always have same parity (+2)
            for (int crossIdx = lowIdx; crossIdx <= highIdx; crossIdx += 2) {
                freeCount += diagonals[crossIdx];
            }
        }
        int grow = forwIdx <= n ? 1 : -1; 
        lowIdx -= grow;
        highIdx+= grow;
    }
    std::cout << freeCount << '\n';
    return 0;
}