AtCoder AT_abc411_c [ABC411C] Black Intervals

题目大意

有 $N$ 个数排成一排，初始值均为 $0$。现在进行 $Q$ 次操作，第 $i$ 次将第 $A_i$ 个数的值反转，请问每次操作后有多少个“黑色区间”。

在这里，我们定义“黑色区间”为满足以下条件的区间 $(l,r)$：

• 第 $l$ 个数到第 $r$ 个数的值均为 $1$。
• 要么满足 $l=1$，要么满足第 $l-1$ 个数的值为 $0$。
• 要么满足 $r=N$，要么满足第 $r+1$ 个数的值为 $0$。

思路

这道题的 $N$ 和 $Q$ 都非常大，所以时间复杂度（包括读入）大概 $O(N+Q)$。发现每次改变第 $A_i$ 个数的值之后，可能影响答案的数只有第 $A_i-1$ 个数和第 $A_i+1$ 个数（如果存在的话），考虑分类讨论：

• 当第 $A_i$ 个数变为 $0$ 时：如果第 $A_i-1$ 个数和第 $A_i+1$ 个数均存在且值均为 $1$，那么这个黑色区间被断开了，答案加一；如果第 $A_i-1$ 个数和第 $A_i+1$ 个数均值为 $0$ 或者不存在，那么一个黑色区间消失了，答案减一；对于其他情况，这里是在某个黑色区间的边缘处减少了一个 $1$，答案不变。
• 当第 $A_i$ 个数变为 $1$ 时：如果第 $A_i-1$ 个数和第 $A_i+1$ 个数均存在且值均为 $1$，那么这两个黑色区间被连起来了，答案减一；如果第 $A_i-1$ 个数和第 $A_i+1$ 个数均值为 $0$ 或者不存在，那么一个新的黑色区间诞生了，答案加一；对于其他情况，这里是在某个黑色区间的边缘处添加了一个 $1$，答案不变。

我们可以根据上面分类讨论的内容完成每次操作。

代码

评测记录：Submission #66939049，已通过。

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int n, q, ans; // n 和 q 含义见读入，ans 表示答案
int col[500010]; // col[i] 代表第 i 个数的值

bool chk(int x) // 判断第 x 个数要么不存在要么值为 0
{
	return !col[x] || x < 1 || x > n;
}

int main()
{
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		col[i] = 0; // 初始化
	while (q--)
	{
		int a;
		cin >> a;
		if (col[a]) // 变成 0
		{
			col[a] = 0; // 改变值
			if (col[a - 1] && col[a + 1])
				ans++; // 黑色区间被断开
			else if (chk(a - 1) && chk(a + 1))
				ans--; // 黑色区间消失
		}
		else
		{
			col[a] = 1;
			if (col[a - 1] && col[a + 1])
				ans--; // 黑色区间被合并
			else if (chk(a - 1) && chk(a + 1))
				ans++; // 黑色区间诞生
		}
		cout << ans << endl;
	}
	return 0;
}

总结

一道偏思维的分类讨论题目，我认为思维难度和代码难度其实也就 $\text{300pts}$ 左右，不是很难，符合 C 题的难度。