103474: [Atcoder]ABC347 E - Set Add Query

Problem Statement

There is an integer sequence $A=(A_1,A_2,\ldots,A_N)$ of length $N$, where all elements are initially set to $0$. Also, there is a set $S$, which is initially empty.

Perform the following $Q$ queries in order. Find the value of each element in the sequence $A$ after processing all $Q$ queries. The $i$-th query is in the following format:

• An integer $x_i$ is given. If the integer $x_i$ is contained in $S$, remove $x_i$ from $S$. Otherwise, insert $x_i$ to $S$. Then, for each $j=1,2,\ldots,N$, add $|S|$ to $A_j$ if $j\in S$.

Here, $|S|$ denotes the number of elements in the set $S$. For example, if $S=\lbrace 3,4,7\rbrace$, then $|S|=3$.

Constraints

• $1\leq N,Q\leq 2\times10^5$
• $1\leq x_i\leq N$
• All given numbers are integers.

Input

The input is given from Standard Input in the following format:

$N$ $Q$
$x_1$ $x_2$ $\ldots$ $x_Q$

Output

Print the sequence $A$ after processing all queries in the following format:

$A_1$ $A_2$ $\ldots$ $A_N$

Sample Input 1

3 4
1 3 3 2

Sample Output 1

6 2 2

In the first query, $1$ is inserted to $S$, making $S=\lbrace 1\rbrace$. Then, $|S|=1$ is added to $A_1$. The sequence becomes $A=(1,0,0)$.

In the second query, $3$ is inserted to $S$, making $S=\lbrace 1,3\rbrace$. Then, $|S|=2$ is added to $A_1$ and $A_3$. The sequence becomes $A=(3,0,2)$.

In the third query, $3$ is removed from $S$, making $S=\lbrace 1\rbrace$. Then, $|S|=1$ is added to $A_1$. The sequence becomes $A=(4,0,2)$.

In the fourth query, $2$ is inserted to $S$, making $S=\lbrace 1,2\rbrace$. Then, $|S|=2$ is added to $A_1$ and $A_2$. The sequence becomes $A=(6,2,2)$.

Eventually, the sequence becomes $A=(6,2,2)$.

Sample Input 2

4 6
1 2 3 2 4 2

Sample Output 2

15 9 12 7

问题描述

有一个长度为$N$的整数序列$A=(A_1,A_2,\ldots,A_N)$，其中所有元素最初都设置为0。此外，还有一个集合$S$，最初为空。

按顺序执行以下$Q$个查询。在处理所有$Q$个查询后，找到序列$A$中每个元素的值。第$i$个查询的格式如下：

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

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

约束条件

• $1\leq N,Q\leq 2\times10^5$
• $1\leq x_i\leq N$
• 给定的所有数字都是整数。

输入

输入从标准输入以以下格式给出：

$N$ $Q$
$x_1$ $x_2$ $\ldots$ $x_Q$

输出

以以下格式打印处理所有查询后的序列$A$：

$A_1$ $A_2$ $\ldots$ $A_N$

样例输入1

3 4
1 3 3 2

样例输出1

6 2 2

在第一个查询中，将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)$。

样例输入2

4 6
1 2 3 2 4 2

样例输出2

15 9 12 7