Ice and Fire

题意翻译

### 题目描述 有$n$个人，第$i$个人的温度为$i$ 环境类型为$0$或$1$.若环境为$0$, 则温度低的人胜利，若环境为$1$, 则温度高的人胜利，$n-1$个环境类型组成一个长为$n-1$的二进制串$s$ 若$x$个人参与游戏，则共有$x-1$场战斗，环境类型即为$s$的前$x-1$个元素.在有不少于$2$个人时，任选$2$个人进行战斗，其中第$i$场战斗的环境类型为$s_i$. 对于任意一个从$2$到$n$的$x$，如果所有温度不超过$x$的人都参与比赛，有多少人有机会获胜（活到最后） ### 输入格式 第一行为整数 $t$，表示测试数据的个数，每个测试数据共两行 每个测试数据的第一行为这个数据的 $n$（$2 \le n \le 2 \cdot 10^5$），表示玩家个数 每个测试数据的第一行为这个数据的 $s$，表示环境类型的排列 ### 输出格式 对于每一个测试数据，一行一共 $n-1$ 个整数，即对于从 $2$ 到 $n$ 的每一个 $x$，有多少人有机会获胜

题目描述

Little09 and his friends are playing a game. There are $ n $ players, and the temperature value of the player $ i $ is $ i $ . The types of environment are expressed as $ 0 $ or $ 1 $ . When two players fight in a specific environment, if its type is $ 0 $ , the player with a lower temperature value in this environment always wins; if it is $ 1 $ , the player with a higher temperature value in this environment always wins. The types of the $ n-1 $ environments form a binary string $ s $ with a length of $ n-1 $ . If there are $ x $ players participating in the game, there will be a total of $ x-1 $ battles, and the types of the $ x-1 $ environments will be the first $ x-1 $ characters of $ s $ . While there is more than one player left in the tournament, choose any two remaining players to fight. The player who loses will be eliminated from the tournament. The type of the environment of battle $ i $ is $ s_i $ . For each $ x $ from $ 2 $ to $ n $ , answer the following question: if all players whose temperature value does not exceed $ x $ participate in the game, how many players have a chance to win?

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1\le t \le 10^3 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 2\leq n\leq 2\cdot 10^5 $ ) — the number of players. The second line of each test case contains a binary string $ s $ with a length $ n-1 $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 3\cdot 10^5 $ .

输出格式

For each test case output $ n-1 $ integers — for each $ x $ from $ 2 $ to $ n $ , output the number of players that have a chance to win.

输入输出样例

输入样例 #1

2
4
001
4
101

输出样例 #1

1 1 3 
1 2 3

说明

In the first test case, for $ x=2 $ and $ x=3 $ , only the player whose temperature value is $ 1 $ can be the winner. For $ x=4 $ , the player whose temperature value is $ 2,3,4 $ can be the winner.

**题目大意**：

有 $ n $ 个人，第 $ i $ 个人的温度为 $ i $。环境类型为 $ 0 $ 或 $ 1 $。如果环境为 $ 0 $，则温度低的人胜利；若环境为 $ 1 $，则温度高的人胜利。$ n-1 $ 个环境类型组成一个长为 $ n-1 $ 的二进制串 $ s $。若 $ x $ 个人参与游戏，则共有 $ x-1 $ 场战斗，环境类型即为 $ s $ 的前 $ x-1 $ 个元素。在有不少于 $ 2 $ 个人时，任选 $ 2 $ 个人进行战斗，其中第 $ i $ 场战斗的环境类型为 $ s_i $。对于任意一个从 $ 2 $ 到 $ n $ 的 $ x $，如果所有温度不超过 $ x $ 的人都参与比赛，问有多少人有机会获胜（活到最后）。

**输入格式**：

第一行为整数 $ t $，表示测试数据的个数，每个测试数据共两行。每个测试数据的第一行为这个数据的 $ n $（$ 2 \le n \le 2 \cdot 10^5 $），表示玩家个数。每个测试数据的第一行为这个数据的 $ s $，表示环境类型的排列。

**输出格式**：

对于每一个测试数据，输出一共 $ n-1 $ 个整数，即对于从 $ 2 $ 到 $ n $ 的每一个 $ x $，输出有多少人有机会获胜。**题目大意**： 有 $ n $ 个人，第 $ i $ 个人的温度为 $ i $。环境类型为 $ 0 $ 或 $ 1 $。如果环境为 $ 0 $，则温度低的人胜利；若环境为 $ 1 $，则温度高的人胜利。$ n-1 $ 个环境类型组成一个长为 $ n-1 $ 的二进制串 $ s $。若 $ x $ 个人参与游戏，则共有 $ x-1 $ 场战斗，环境类型即为 $ s $ 的前 $ x-1 $ 个元素。在有不少于 $ 2 $ 个人时，任选 $ 2 $ 个人进行战斗，其中第 $ i $ 场战斗的环境类型为 $ s_i $。对于任意一个从 $ 2 $ 到 $ n $ 的 $ x $，如果所有温度不超过 $ x $ 的人都参与比赛，问有多少人有机会获胜（活到最后）。 **输入格式**： 第一行为整数 $ t $，表示测试数据的个数，每个测试数据共两行。每个测试数据的第一行为这个数据的 $ n $（$ 2 \le n \le 2 \cdot 10^5 $），表示玩家个数。每个测试数据的第一行为这个数据的 $ s $，表示环境类型的排列。 **输出格式**： 对于每一个测试数据，输出一共 $ n-1 $ 个整数，即对于从 $ 2 $ 到 $ n $ 的每一个 $ x $，输出有多少人有机会获胜。