codeforces 704A (队列模拟) Thor

下面是“Codeforces 704A Thor”的完整攻略，包括题目描述、解题思路和两个示例等方面。

题目描述

有 $n$ 个应用程序，每个应用程序都有一个通知。现在，你需要实现一个通知中心，支持以下两种操作：

1. 将某个应用程序的通知加入通知中心。
2. 将通知中心中某个应用程序的通知全部清空。

其中，第一种操作的时间复杂度为 $O(1)$，第二种操作的时间复杂度为 $O(n)$。

解题思路

对于这道题目，我们可以使用队列来实现通知中心。具体思路如下：

1. 首先，我们可以使用一个数组 q 来表示队列，其中 q[i] 表示应用程序 $i$ 的通知数量。
2. 对于第一种操作，我们只需要将对应应用程序的通知数量加 $1$ 即可，时间复杂度为 $O(1)$。
3. 对于第二种操作，我们需要遍历整个队列，将对应应用程序的通知数量清零，时间复杂度为 $O(n)$。

需要注意的是，由于第二种操作的时间复杂度较高，因此我们需要尽量减少其出现的次数。具体来说，我们可以使用一个变量 last 来记录上一次清空操作的位置，每次清空操作时，只需要从 last 开始遍历即可。

示例说明

下面是两个示例，分别演示了输入样例和输出结果。

示例1

输入：

5
1 1
1 2
1 3
2 1
1 4

输出：

1
1
1
0

在上述示例中，输入了 $5$ 个操作，其中第 $i$ 个操作表示对应的应用程序执行的操作。根据题目描述，我们可以得到输出结果为 $1,1,1,0$。

示例2

输入：

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

输出：

1
1
1
1
1
0
0
0
0
0

在上述示例中，输入了 $10$ 个操作，其中前 $5$ 个操作是添加操作，后 $5$ 个操作是清空操作。根据题目描述，我们可以得到输出结果为 $1,1,1,1,1,0,0,0,0,0$。

结论

本文为您提供了“Codeforces 704A Thor”的完整攻略，包括题目描述、解题思路和两个示例说明等方面。在实际应用中，可以根据具体需求选择不同的数据结构，从而实现高效的操作。