AT_abc203_e [ABC203E] White Pawn

题目描述

设N NN为正整数。有一个( 2 N + 1 ) × ( 2 N + 1 ) (2N+1)\times (2N+1)(2N+1)×(2N+1)的棋盘，行和列的编号分别为0 00到2 N 2N2N，位于第i ii行第j jj列的格子记作( i , j ) (i,j)(i,j)。

棋盘上有一个白色兵，最初放在( 0 , N ) (0,N)(0,N)。有M MM个黑色兵，第i ii个黑色兵放在( X i , Y i ) (X_i, Y_i)(Xi​,Yi​)。

当白色兵在( i , j ) (i,j)(i,j)时，你可以通过以下任一操作移动白色兵：

• 若0 ≤ i ≤ 2 N − 1 0\leq i\leq 2N-10≤i≤2N−1，0 ≤ j ≤ 2 N 0\leq j\leq 2N0≤j≤2N，且( i + 1 , j ) (i+1,j)(i+1,j)没有黑色兵，则可以将白色兵移动到( i + 1 , j ) (i+1,j)(i+1,j)。
• 若0 ≤ i ≤ 2 N − 1 0\leq i\leq 2N-10≤i≤2N−1，0 ≤ j ≤ 2 N − 1 0\leq j\leq 2N-10≤j≤2N−1，且( i + 1 , j + 1 ) (i+1,j+1)(i+1,j+1)有黑色兵，则可以将白色兵移动到( i + 1 , j + 1 ) (i+1,j+1)(i+1,j+1)。
• 若0 ≤ i ≤ 2 N − 1 0\leq i\leq 2N-10≤i≤2N−1，1 ≤ j ≤ 2 N 1\leq j\leq 2N1≤j≤2N，且( i + 1 , j − 1 ) (i+1,j-1)(i+1,j−1)有黑色兵，则可以将白色兵移动到( i + 1 , j − 1 ) (i+1,j-1)(i+1,j−1)。

黑色兵不能移动。

请你求出，经过若干次操作后，白色兵最终可以到达( 2 N , Y ) (2N,Y)(2N,Y)的不同Y YY的个数。

输入格式

输入通过标准输入给出，格式如下：

N NNM MMX 1 X_1X1​Y 1 Y_1Y1​: ::X M X_MXM​Y M Y_MYM​

输出格式

输出答案。

输入输出样例 #1

输入 #1

2 4 1 1 1 2 2 0 4 2

输出 #1

3

输入输出样例 #2

输入 #2

1 1 1 1

输出 #2

0

说明/提示

限制条件

• 1 ≤ N ≤ 10 9 1\leq N\leq 10^91≤N≤109
• 0 ≤ M ≤ 2 × 10 5 0\leq M\leq 2\times 10^50≤M≤2×105
• 1 ≤ X i ≤ 2 N 1\leq X_i\leq 2N1≤Xi​≤2N
• 0 ≤ Y i ≤ 2 N 0\leq Y_i\leq 2N0≤Yi​≤2N
• ( X i , Y i ) ≠ ( X j , Y j ) (X_i, Y_i)\neq (X_j, Y_j)(Xi​,Yi​)=(Xj​,Yj​)（i ≠ j i\neq ji=j）
• 所有输入均为整数。

样例解释 1

可以分别如下移动到( 4 , 0 ) (4,0)(4,0)、( 4 , 1 ) (4,1)(4,1)、( 4 , 2 ) (4,2)(4,2)这三个位置：

• ( 0 , 2 ) → ( 1 , 1 ) → ( 2 , 1 ) → ( 3 , 1 ) → ( 4 , 2 ) (0,2)\to (1,1)\to (2,1)\to (3,1)\to (4,2)(0,2)→(1,1)→(2,1)→(3,1)→(4,2)
• ( 0 , 2 ) → ( 1 , 1 ) → ( 2 , 1 ) → ( 3 , 1 ) → ( 4 , 1 ) (0,2)\to (1,1)\to (2,1)\to (3,1)\to (4,1)(0,2)→(1,1)→(2,1)→(3,1)→(4,1)
• ( 0 , 2 ) → ( 1 , 1 ) → ( 2 , 0 ) → ( 3 , 0 ) → ( 4 , 0 ) (0,2)\to (1,1)\to (2,0)\to (3,0)\to (4,0)(0,2)→(1,1)→(2,0)→(3,0)→(4,0)

另一方面，无法移动到( 4 , 3 ) (4,3)(4,3)和( 4 , 4 ) (4,4)(4,4)。因此，输出3 33。

样例解释 2

无法将白色兵从( 0 , 1 ) (0,1)(0,1)移动到其他位置。

由 ChatGPT 4.1 翻译

题解

简要题意：

简单模拟一下样例就会发现：

• 如果一行一个黑子都没有，那么对答案没有帮助，原来位置的白子直接下移一格即可
• 如果白子想脱离横坐标 N，只能是借助斜下方的黑子
  所以我们只要枚举所有黑子的位置去讨论答案就好了（呼应了M<=2e5但N<=1e9的数据范围）

看起来有点像dp的转移，可以考虑从上到下枚举有黑子的行，存储当前所有白子可能出现的列集合S（最多2N个）；
再枚举当前行的黑子，判断两个事：

• 其斜上方是否存在白子，若存在，把它的纵列加入S
• 其正上方是否存在白子，若存在，把它的纵列从S中移出（因为正下方有黑子时白子没办法继续下移了）

存储黑子可以用map，自动按照第一、二维排序。
考虑如何维护集合S，发现我们需要快速查找是否存在对应下标以及插入、删除操作，不难想到用set维护
时间复杂度降至O(mlogm)

// code by https://www.luogu.com.cn/article/ref58umu#include<bits/stdc++.h>#definelllonglongusingnamespacestd;intmain(){intn,m;scanf("%d%d",&n,&m);map<int,vector<int>>Map;set<int>Set;for(inti=1;i<=m;i++){intx,y;scanf("%d%d",&x,&y);Map[x].push_back(y);}Set.insert(n);for(autoi:Map){vector<int>in,out;for(intj:i.second){if(Set.count(j))out.push_back(j);if(Set.count(j-1)||Set.count(j+1))in.push_back(j);}for(intj:out)Set.erase(j);for(intj:in)Set.insert(j);}printf("%d",Set.size());return0;}