Set Add Query

题目描述

有一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$，所有元素初始都设为 $0$。另外，有一个集合 $S$，初始为空。 按顺序执行下面的 $Q$ 个查询。请在处理完所有 $Q$ 个查询后，求序列 $A$ 中每个元素的值。第 $i$ 个查询格式如下：

给定一个整数 $x_i$。如果整数 $x_i$ 已包含在 $S$ 中，则将 $x_i$ 从 $S$ 中移除。否则，将 $x_i$ 插入到 $S$ 中。然后，对于每个 $j=1,2,\ldots,N$，如果 $j\in S$，则对 $A_j$ 加上 $|S|$。

这里，$|S|$ 表示集合 $S$ 中元素的个数。例如，如果 $S=\lbrace 3,4,7\rbrace$，那么 $|S|=3$。

输入格式

输入从标准输入以以下格式给出： $N$ $Q$ $x_1$ $x_2$ $\ldots$ $x_Q$

输出格式

在处理完所有查询后按以下格式输出序列 $A$： $A_1$ $A_2$ $\ldots$ $A_N$

3 4
1 3 3 2

6 2 2

4 6
1 2 3 2 4 2

15 9 12 7

提示

$1\leq N,Q\leq 2\times10^5$ $1\leq x_i\leq N$ 所有给定的数均为整数。在第一个查询中，将 $1$ 插入到 $S$，使得 $S=\lbrace 1\rbrace$。然后，将 $|S|=1$ 加到 $A_1$。序列变为 $A=(1,0,0)$。 在第二个查询中，将 $3$ 插入到 $S$，使得 $S=\lbrace 1,3\rbrace$。然后，将 $|S|=2$ 加到 $A_1$ 和 $A_3$。序列变为 $A=(3,0,2)$。 在第三个查询中，将 $3$ 从 $S$ 中移除，得到 $S=\lbrace 1\rbrace$。然后，将 $|S|=1$ 加到 $A_1$。序列变为 $A=(4,0,2)$。 在第四个查询中，将 $2$ 插入到 $S$，使得 $S=\lbrace 1,2\rbrace$。然后，将 $|S|=2$ 加到 $A_1$ 和 $A_2$。序列变为 $A=(6,2,2)$。 最终，序列变为 $A=(6,2,2)$。

标签: AtCoder|abc347E

来源

AtCoder|abc347E