解题思路

对每个位置 $i$ ，需要统计左侧与 $s_i$ 不同的字符个数。用两个计数器 $\mathrm{cnt0}$ 、 $\mathrm{cnt1}$ 记录已经扫过的 0 与 1 的个数。

从左到右扫描：若当前是 0，则答案为当前的 $\mathrm{cnt1}$ ，随后 $\mathrm{cnt0}$ 加一；若当前是 1，则答案为当前的 $\mathrm{cnt0}$ ，随后 $\mathrm{cnt1}$ 加一。一次扫描即可得到全部 $a_i$ 。

复杂度分析

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ （用于存放答案）。

某设备会依次记录 $n$ 次运行状态，每次状态只有两种，分别用字符 0 和 1 表示。

所有记录按照时间顺序组成一个长度为 $n$ 的字符串

s=s_1s_2\ldots s_n