← 返回题目列表

AtCoder · abc347_e

H. 设置添加查询

中文机器翻译题面 查看原题

分数: 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