AT_abc347_e [ABC347E] 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$，则将 $|S|$ 加到 $A_j$ 上。

其中，$|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$

输入输出样例 #1

输入 #1

3 4
1 3 3 2

输出 #1

6 2 2

输入输出样例 #2

输入 #2

4 6
1 2 3 2 4 2

输出 #2

15 9 12 7

说明/提示

限制条件

• $1\leq N,Q\leq 2\times 10^5$
• $1\leq x_i\leq N$
• 输入的所有数均为整数

样例解释 1

第 $1$ 个查询，将 $1$ 加入 $S$，此时 $S=\lbrace 1\rbrace$。然后，$A_1$ 加上 $|S|=1$，$A=(1,0,0)$。

第 $2$ 个查询，将 $3$ 加入 $S$，此时 $S=\lbrace 1,3\rbrace$。然后，$A_1,A_3$ 各加上 $|S|=2$，$A=(3,0,2)$。

第 $3$ 个查询，将 $3$ 从 $S$ 中删除，$S=\lbrace 1\rbrace$。然后，$A_1$ 加上 $|S|=1$，$A=(4,0,2)$。

第 $4$ 个查询，将 $2$ 加入 $S$，$S=\lbrace 1,2\rbrace$。然后，$A_1,A_2$ 各加上 $|S|=2$，$A=(6,2,2)$。

最终，$A=(6,2,2)$。

由 ChatGPT 4.1 翻译