Set Add Query

AtCoder

IDabc347_e

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

3 4
1 3 3 2

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)$.

Input #2

4 6
1 2 3 2 4 2

Output #2

15 9 12 7

API Response (JSON)

{
  "problem": {
    "name": "Set Add Query",
    "description": {
      "content": "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 ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc347_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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.\nPerform the following $Q$ queries ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments