/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
全ての要素が 0 で初期化された長さ N の整数列 A=(A_1,A_2,\ldots,A_N) があります。また、集合 S があります。はじめ S は空です。
以下の Q 個のクエリを順に行います。Q 個のクエリを全て処理した後の数列 A の各要素の値を求めてください。 i 番目のクエリは以下の形式です。
- 整数 x_i が与えられる。整数 x_i が S に含まれる場合、S から x_i を削除する。そうでない場合、S に x_i を追加する。次に、j=1,2,\ldots,N について、j\in S ならば A_j に |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 に 1 を追加し、S=\lbrace 1\rbrace となります。その後、A_1 に |S|=1 を加算します。A=(1,0,0) となります。
2 番目のクエリでは、S に 3 を追加し、S=\lbrace 1,3\rbrace となります。その後、A_1,A_3 に |S|=2 を加算します。A=(3,0,2) となります。
3 番目のクエリでは、S から 3 を削除し、S=\lbrace 1\rbrace となります。その後、A_1 に |S|=1 を加算します。A=(4,0,2) となります。
4 番目のクエリでは、S に 2 を追加し、S=\lbrace 1,2\rbrace となります。その後、A_1,A_2 に |S|=2 を加算します。A=(6,2,2) となります。
最終的に、A=(6,2,2) となります。
入力例 2
4 6 1 2 3 2 4 2
出力例 2
15 9 12 7
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