P15992 [PA 2026] Original Problem Harder Version 2 / Wersja dla profesjonalistów 2

$\large{\bf{{Warning: Abusing this problem’s judging system will result in an account ban even for a single attempt.}}}$

In $2014$, the following problem appeared in the finals of the 8th Junior High School Informatics Olympiad: > **Hopscotch** > > Jasiu likes playing hopscotch with his friends. They decided to slightly improve the rules of the game. At the beginning, $N$ square cells are drawn on the sidewalk, arranged in a line. The cells are numbered starting from $1$ on the left. Some cells contain a single small stone. Each player chooses a starting cell and an integer $K$ greater than $1$. Then, starting from the chosen cell, they jump by $K$ cells each time, until they jump past cell $N$. The player’s score equals the number of landings that are on cells containing stones. Now it is Jasiu’s turn, and he really wants to get the highest possible score. Given the stone positions, compute the maximum score he can obtain. > > ###

> The first line of standard input is an integer $N$ ($1 \le N \le 10^6$), the number of cells. The second line is a string of length $N$ consisting of characters `.` and/or `#`. If the $i$-th character is `#`, then the $i$-th cell contains a stone; otherwise, the cell is empty. > > ###

> The only line of standard output should print one integer, the maximum score Jasiu can obtain. > > #### Examples > > | Input: | Input: | Input: | > |--------|--------|--------| > | $\texttt{8}\\\texttt{\#..\#...\#}$ | $\texttt{6}\\\texttt{\#\#\#\#..}$ | $\texttt{9}\\\texttt{\#.\#..\#..\#}$ | > | Output: | Output: | Output: | > | `2` | `2` | `3` | The junior high school students from $2014$ are now professional contestants participating in PA, so we can expect that they are interested in a significantly harder problem. In this version, the stone arrangement is not fixed from the start—we begin with an empty board of $n$ cells, and the kids keep adding and removing stones. After each operation, Jasiu needs to determine the maximum score he can obtain. **Note:** You can also find an editorial for that (original) problem online; for convenience, we include it here: `https://www.youtube.com/live/jxYu1MGGjBc`. However, we do not guarantee that the information there will be helpful for solving this version of the problem. # Input Format The first line contains two integers $n$ and $q$ ($1 \le n < 10\,000\,000$, $1 \le q < 1\,000\,000$). The next $q$ lines each describe one event. The description of the $i$-th event is an integer $a_i$ ($1 \le a_i \le n$), meaning: if there is no stone on cell $a_i$, place one there; if there is already a stone there, remove it. # Output Format For each operation, output one integer: the maximum score Jasiu can obtain after this operation.

### Explanation of the examples After the first three operations, the board state is the same as the first (leftmost) case in the original problem (more precisely, there is an extra 9th empty cell, but it does not affect the result). After three more operations, we get the second (middle) case, and finally we get the third (rightmost) case. Translated by ChatGPT 5