题目描述

难度分:$1400$

输入$n(2 \leq n \leq 10^5)$和$q(1 \leq q \leq 10^5)$。

有一个$2$行$n$列的网格图，一开始所有格子都是空的。行列编号从$1$开始。

然后输入$q$个操作，每个操作输入两个数$r$，$c$，表示切换$r$行$c$列这个格子的状态：从空格子变成障碍格子，或者从障碍格子变成空格子。

对于每个询问，判断能否从左上角走到右下角，输出Yes或No。你只能走上下左右的相邻格子，且不能走到障碍格子上。

注：如果起点或终点变成障碍，直接输出No。

输入样例

5 5
2 3
1 4
2 4
2 3
1 4

输出样例

Yes
No
No
No
Yes

算法

模拟

准备一个$2 \times n$的矩阵$grid$进行模拟，翻转操作其实就是$grid[r][c]=1-grid[r][c]$。

如果翻转后$grid[r][c]=1$，那么此时就可能出现阻断，用一个四元组来表示阻断类型。$r=1$时，分为以下三种情况：

1. $grid[r+1][c]=1$，就存在一条竖直阻断$(r,c,r+1,c)$，将其加入到一个有序集合（也可以哈希集合，但是要重写哈希函数）中。
2. $grid[r+1][c+1]=1$，就存在一条斜向右下的阻断$(r,c,r+1,c+1)$，将其加入集合。
3. $grid[r+1][c-1]$，就存在一条斜向左下的阻断$(r,c,r+1,c-1)$，将其加入集合。

同理考虑$r=2$时的情况。

如果翻转后$grid[r][c]=0$，就检查一下与$(r,c)$有关的阻断是否存在于集合中，存在就将其从集合中删除。这种情况无脑删就可以了，比添加阻断时简单很多，但是需要注意四元组的顺序需要和插入时保持一致，即前两个元素是$r=1$的格子，后两个元素是$r=2$的格子。

对于每条操作，检查一下集合中是否存在阻断就能判断$(1,1)$到$(2,n)$是否连通，没有阻断就是连通的。

复杂度分析

时间复杂度

初始化矩阵的时间复杂度为$O(n)$。每条操作存在对集合的插入和删除操作，如果是有序集合时间复杂度就是$O(log_2n)$，所有操作的时间复杂度为$O(qlog_2n)$，哈希集合时间复杂度就是$O(1)$，所有操作的时间复杂度为$O(q)$。

综上，整个算法的时间复杂度为$O(n+q)$（或$O(n+qlog_2n)$）。

空间复杂度

矩阵的空间消耗是$O(n)$级别，集合的空间消耗也是$O(n)$级别，因为每个单元格最多牵涉到$3$条阻断。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;
int n, q, grid[3][N];

int main() {
    scanf("%d%d", &n, &q);
    bool ok = true, fuck = false;
    memset(grid, 0, sizeof(grid));
    set<array<int, 4>> block;
    while(q--) {
        int r, c;
        scanf("%d%d", &r, &c);
        grid[r][c] = 1 - grid[r][c];
        if(grid[1][1] == 1 || grid[2][n] == 1) {
            fuck = true;
        }
        if(grid[1][1] == 0 && grid[2][n] == 0) {
            fuck = false;
        }
        if(grid[r][c] == 1) {
            if(r == 1) {
                if(grid[r + 1][c] == 1) {
                    block.insert({r, c, r + 1, c});
                }
                if(grid[r + 1][c - 1] == 1) {
                    block.insert({r, c, r + 1, c - 1});
                }
                if(grid[r + 1][c + 1] == 1) {
                    block.insert({r, c, r + 1, c + 1});
                }
            }else {
                if(grid[r - 1][c] == 1) {
                    block.insert({r - 1, c, r, c});
                }
                if(grid[r - 1][c - 1] == 1) {
                    block.insert({r - 1, c - 1, r, c});
                }
                if(grid[r - 1][c + 1] == 1) {
                    block.insert({r - 1, c + 1, r, c});
                }
            }
        }else {
            if(r == 1) {
                block.erase({r, c, r + 1, c});
                block.erase({r, c, r + 1, c - 1});
                block.erase({r, c, r + 1, c + 1});
            }else {
                block.erase({r - 1, c, r, c});
                block.erase({r - 1, c - 1, r, c});
                block.erase({r - 1, c + 1, r, c});
            }
        }
        puts(block.empty() && !fuck? "Yes": "No");
    }
    return 0;
}