徐老师的多米诺
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
徐老师在一个 $n * n$ 的矩形网格的正中间放了共计 $(n - 2) * (n - 2)$ 个正方形多米诺骨牌
如下形状（用 $1$ 表示多米诺骨牌，$0$ 表示为空)：
```
000000
011110
011110
011110
011110
000000
```
接下来徐老师会进行 $Q$ 次操作，操作分为两种：
1. 从左往右推倒 $(i,2)$ 的多米诺骨牌
2. 从上往下推倒 $(2,i)$ 的多米诺骨牌
众所周知，多米诺骨牌在被推倒时，会连带把倒向的多米诺骨牌一起推倒，直到该方向下一格没有多米诺骨牌为止
例如如上的网格，徐老师从上往下推倒 $(2,4)$ 的多米诺骨牌后变为
```
000000
011010
011010
011010
011010
000000
```
接着徐老师从左往右推倒 $(4,2)$ 的多米诺骨牌：
```
000000
011010
011010
000010
011010
000000
```
现在徐老师想知道，$T$ 次操作以后，网格上还有多少多米诺骨牌还没倒？
输入格式
第一行输入两个正整数 $n,T$， 表示网格大小和操作次数接下来 $T$ 行，每行包含两个整数 $op, x$
若 $op == 1$ 表示徐老师从上往下推倒了 $(2,x)$ 这块多米诺骨牌
若 $op == 2$ 表示徐老师从上往下推倒了 $(x,2)$ 这块多米诺骨牌
对于 $30\%$ 的数据：$n \leq 2000$。
对于 $70\%$ 的数据：时限$1$s。
对于最后 $30\%$ 的数据：时限 $100ms$。
对于 $100\%$ 的数据：$n \leq 2\times 10^5,1\leq T \leq \min(2n-4,2\times 10^5),2\leq x\leq n-1$
特别的保证：徐老师不会推倒同一块多米诺骨牌
输出格式
输出一个整数，表示还没倒的多米诺骨牌数量样例
6 2
1 4
2 4102023暑CSP-S复赛集训模拟赛二
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2023-7-29 22:00
- 结束于
- 2023-8-8 22:00
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 22
