Controversial Rounds
Contest: Educational Codeforces Round 93 (Rated for Div. 2)
Difficulty rating: 2500
Tags: binary search, data structures, dp, greedy, two pointers

Alice and Bob play a game. The game consists of several sets, and each set consists of several rounds. Each round is won either by Alice or by Bob, and the set ends when one of the players has won $$$x$$$ rounds in a row. For example, if Bob won five rounds in a row and $$$x = 2$$$, then two sets ends.

You know that Alice and Bob have already played $$$n$$$ rounds, and you know the results of some rounds. For each $$$x$$$ from $$$1$$$ to $$$n$$$, calculate the maximum possible number of sets that could have already finished if each set lasts until one of the players wins $$$x$$$ rounds in a row. It is possible that the last set is still not finished — in that case, you should not count it in the answer.

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the number of rounds.

The second line contains one string $$$s$$$ of length $$$n$$$ — the descriptions of rounds. If the $$$i$$$-th element of the string is 0, then Alice won the $$$i$$$-th round; if it is 1, then Bob won the $$$i$$$-th round, and if it is ?, then you don't know who won the $$$i$$$-th round.

Output format:
In the only line print $$$n$$$ integers. The $$$i$$$-th integer should be equal to the maximum possible number of sets that could have already finished if each set lasts until one of the players wins $$$i$$$ rounds in a row.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Let's consider the first test case:

- if $$$x = 1$$$ and $$$s = 110000$$$ or $$$s = 111000$$$ then there are six finished sets;
- if $$$x = 2$$$ and $$$s = 110000$$$ then there are three finished sets;
- if $$$x = 3$$$ and $$$s = 111000$$$ then there are two finished sets;
- if $$$x = 4$$$ and $$$s = 110000$$$ then there is one finished set;
- if $$$x = 5$$$ then there are no finished sets;
- if $$$x = 6$$$ then there are no finished sets.

Example input:
6
11?000

Example output:
6 3 2 1 0 0

Example input:
5
01?01

Example output:
5 1 0 0 0

Editorial:
Let's consider the following function $$$f(pos, x)$$$: minimum index $$$npos$$$ such that there is a substring of string $$$s_{pos}, s_{pos+1}, \dots, s_{npos-1}$$$ of length $$$x$$$ consisting of only characters $$$1$$$ and $$$?$$$ or $$$0$$$ and $$$?$$$. If this function has asymptotic $$$O(1)$$$ then we can solve problem for $$$O(n log n)$$$.
Now, let's precalculate two array $$$nxt0$$$ and $$$nxt1$$$; $$$nxt0[i]$$$ is equal the maximum integer $$$len$$$ such that substring $$$s_i, s_{i+1}, \dots, s_{i+len-1}$$$ consist only characters $$$1$$$ and $$$?$$$. $$$nxt1[i]$$$ is equal the maximum integer $$$len$$$ such that substring $$$s_i, s_{i+1}, \dots, s_{i+len-1}$$$ consist only characters $$$0$$$ and $$$?$$$.
Also let's precalculate the arrays $$$p0$$$ and $$$p1$$$ of size $$$n$$$; $$$p0[len]$$$ contain all positions $$$pos$$$ such that substring $$$s_{pos}, s_{pos+1}, \dots, s_{pos+len-1}$$$ consist only characters $$$1$$$ and $$$?$$$ and $$$pos = 0$$$ or $$$s_{pos - 1} = 0$$$; $$$p1[len]$$$ contain all positions $$$pos$$$ such that substring $$$s_{pos}, s_{pos+1}, \dots, s_{pos+len-1}$$$ consist only characters $$$0$$$ and $$$?$$$ and $$$pos = 0$$$ or $$$s_{pos - 1} = 1$$$.
After that let's solve problem for some $$$x$$$. Suppose, that now we already processed first $$$pos$$$ elements of $$$s$$$. If $$$nxt0[pos] \ge x$$$ or $$$nxt1[pos] \ge x$$$ then we increase the answer and change $$$pos = pos + x$$$. Otherwise we have to find the minimum element (denote this element as $$$npos$$$) in $$$p0[x]$$$ or $$$p1[x]$$$ such that $$$npos \ge pos$$$. If there is no such element then we found the final answer . Otherwise let's increase answer and change $$$pos = npos + x$$$ and continue this algorithm.