P9883 [EC Final 2021] Fenwick Tree

庞教授正在讲授关于 Fenwick 树（也称为二叉索引树）的课程。 在 Fenwick 树中，我们有一个长度为 $n$ 的数组 $c[1\ldots n]$，初始时全为零（对于任何 $1\le i\le n$，$c[i]=0$）。每次，庞教授可以对某个位置 $pos$（$1\leq pos \leq n$）和一个值 $val$ 调用以下过程： ```cpp def update(pos, val): while (pos

第一行包含一个整数 $T~(1 \le T \le 10^5)$，表示测试用例的数量。 对于每个测试用例，第一行包含一个整数 $n~(1 \le n \le 10 ^ 5)$。下一行包含一个长度为 $n$ 的字符串。如果 $c[i]$ 非零，则字符串的第 $i$ 个字符为 `1`，否则为 `0`。 保证所有测试用例中 $n$ 的总和不超过 $10^6$。

对于每个测试用例，输出庞教授调用该过程的最小可能次数。可以证明答案总是存在的。

对于第一个例子，庞教授可以依次调用 `update(1,1)`，`update(2,-1)`，`update(3,1)`。 对于第三个例子，庞教授可以依次调用 `update(1,1)`，`update(3,1)`，`update(5,1)`。 题面翻译由 ChatGPT-4o 提供。