怎么会有这么变态的题目。

首先不难注意到美感值的“贡献”只会在一整段 $0$ 和一整段 $1$ 之间。所以先把原序列“缩点”，将极长的相同字符区间缩成一个点。

假设当前的美感值和分成段数是已知的，设它们分别为 $m,k$，显然二元组 $(m,k)$ 的数量大致是调和级数级别，为 $O(n \log n)$。
而且对于一个 $(m,k)$，它会产生贡献的前缀答案为一段区间 $[l,r]$。可以用数学归纳法证明：

• 考虑 $k=1$，那么只有 $[m,m]$ 区间有贡献。
• 考虑 $k + 1 \to k$。
  • 会导致 $r \to r + m + 1$。即拼成 $m$ 美感值需要 $m+1$ 段。
  • 如果当前第 $l$ 段在原序列只有一个点，那么 $l \to l + m + 1$，因为不能通过切割当前 $l$ 的一部分后缀和后面拼凑。
  • 如果第 $l$ 段在原序列有多个点，那么 $l \to l + m$，因为可以保留一部分 $l$ 的点和后面 $m$ 段匹配。

考虑模拟这个过程，枚举 $m$ 再逐步增加 $k$。对一段区间有贡献，考虑差分维护。
另外我们只计算了 $m \gt 0$ 的贡献，需要额外计算 $m=0$。
当 $m=0$ 的时候，答案下界是每段分一个，即当前是第几段 $i$；上界是每个点分一个，即当前是原序列第几个点 $now$，答案即为 $now-i+1$。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 15;
int T, n, len[N], tot = 0;
int b[N];
char s[N];
void solve() {
    scanf("\n %d\n %s", &n, s + 1), len[tot = 1] = 1, b[tot] = 0;
    for (int i = 2; i <= n; i++)
        if (s[i] ^ s[i - 1]) len[++tot] = 1, b[tot] = 0;
        else len[tot]++;
    for (int m = 1; m < tot; m++) {
        int l = m + 1, r = m + 1;   // 从 m+1 开始因为需要凑出 m 美丽值
        while (l <= tot) b[l]++, b[r + 1]--, l += m + (len[l] == 1), r += m + 1;
    }
    int now = 0;
    for (int i = 1; i <= tot; i++) {
        b[i] += b[i - 1];
        while (len[i]--) now++, printf("%d ", b[i] + (now - i + 1) );
    } puts("");
}

int main() {
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}