103474: [Atcoder]ABC347 E - Set Add Query
Description
Score: $500$ points
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
Input
Output
问题描述
有一个长度为$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