解题思路

设当前整数为 $x$，每次操作后要输出 $x$ 的二进制中 $1$ 的个数。

如果每次真的去维护大整数，再重新统计二进制里 $1$ 的数量，那么在数据范围 $n \le 10^6$ 下显然不合适。 因此这里使用的核心算法是：用二进制的“连续段”来模拟，也就是维护二进制表示的运行长度编码（$RLE$）。

核心思路

题目内容

给定一个初始值为$0$的整数$x$和一个仅由字符$+、-、*、/$ 组成的字符串$s$，表示一系列操作。

依次对$s$中的每个字符执行以下操作：

若字符为$+$，将$x$增加$1$；若字符为-，将$x$减少$1$，但保持$x≥0$；

若字符为*，将$x$乘以$2$；若字符为$/$，将x除以$2$并向下取整。每次操作后，输出$x$的二进制表示中1的个数。

输入描述

第一行输入一个整数$n (1 ≤ n ≤ 10^6)$，表示操作次数；

第二行输入一个长度为n的字符串$s$，仅包含字符$+，-，*，/，$表示操作序列。

输出描述

输出$n$行，每行输出一个整数，表示对应操作执行后$x$的二进制表示中$1$的个数。

样例1

输入

7
++-*-//

输出

1
1
1
1
1
0
0