题目详情题解（0）讨论（0）提交记录（0）

AT_abc179_f.[ABC179F] Simplified Reversi

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个纵向 NN 格、横向 NN 格的网格。第 ii 行第 jj 列的格子记作 (i,j)(i, j)。

在网格中央的 (N−2)×(N−2)(N-2) \times (N-2) 个格子中，每个格子上都放有一颗黑色石子。在下边界和右边界共 2N−12N-1 个格子上，每个格子上都放有一颗白色石子。

现在给出 QQ 个查询，请按顺序处理。查询有两种类型，输入格式和内容如下：

  • 1 x：在 (1,x)(1, x) 处放置一颗白色石子。然后，将从该位置向下直到遇到最近的白色石子之间的所有黑色石子替换为白色石子。
  • 2 x：在 (x,1)(x, 1) 处放置一颗白色石子。然后，将从该位置向右直到遇到最近的白色石子之间的所有黑色石子替换为白色石子。

请在处理完所有 QQ 个查询后，输出网格上剩余的黑色石子的数量。

输入格式

输入以以下格式从标准输入读入。

NN QQ
Query1Query_1
⋮\vdots
QueryQQuery_Q

输出格式

请输出处理完所有 QQ 个查询后，网格上剩余的黑色石子的数量。

输入输出样例

  • 输入#1

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

    输出#1

    1

  • 输入#2

    200000 0

    输出#2

    39999200004

  • 输入#3

    176527 15
1 81279
2 22308
2 133061
1 80744
2 44603
1 170938
2 139754
2 15220
1 172794
1 159290
2 156968
1 56426
2 77429
1 97459
2 71282

    输出#3

    31159505795

说明/提示

限制条件

  • 3≤N≤2×1053 \leq N \leq 2 \times 10^5
  • 0≤Q≤min⁡(2N−4,2×105)0 \leq Q \leq \min(2N-4, 2 \times 10^5)
  • 2≤x≤N−12 \leq x \leq N-1
  • 不会有重复的查询

样例解释 1

每次查询后，网格的变化如下图所示。
图

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页