分数: 500 点
问题陈述
有一个整数序列 A=(A_1,A_2,\ldots,A_N) 长度 N,其中所有元素最初设置为 0。另外,还有一套 S,最初是空的。
执行以下操作 Q 按顺序查询。查找序列中每个元素的值 A 处理完所有内容后 Q 查询。的 i-第一个查询的格式如下:
- 一个整数 给出了 x_i 。如果整数 x_i 包含在 S,删除 x_i 来自 S。否则,插入 x_i to S。然后,对于每个 j=1,2,\ldots,N,添加 |S| to A_j if j\in S.
在这里, |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