CF1381A2 Prefix Flip (Hard Version)

这是该问题的困难版本。不同版本的区别在于 $n$ 的约束和所需操作次数。只有在所有版本的问题都被解决后，才能进行 Hack。 有两个长度为 $n$ 的二进制字符串 $a$ 和 $b$（二进制字符串是仅由 $0$ 和 $1$ 组成的字符串）。每次操作，你可以选择 $a$ 的一个前缀，同时将该前缀中的所有位取反（$0$ 变为 $1$，$1$ 变为 $0$），并将该前缀的顺序反转。 例如，如果 $a=001011$，你选择长度为 $3$ 的前缀后，$a$ 变为 $011011$。然后如果你选择整个字符串作为前缀，$a$ 变为 $001001$。 你的任务是在最多 $2n$ 次操作内，将字符串 $a$ 变换为 $b$。可以证明总是存在可行解。

第一行包含一个整数 $t$（$1\le t\le 1000$），表示测试用例的数量。接下来的 $3t$ 行描述每个测试用例。 每个测试用例的第一行包含一个整数 $n$（$1\le n\le 10^5$），表示二进制字符串的长度。 接下来的两行分别包含两个长度为 $n$ 的二进制字符串 $a$ 和 $b$。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出一个整数 $k$（$0\le k\le 2n$），表示你所用的操作次数，接着输出 $k$ 个整数 $p_1,\ldots,p_k$（$1\le p_i\le n$），其中 $p_i$ 表示第 $i$ 次操作时翻转的前缀长度。

在第一个测试用例中，有 $01\to 11\to 00\to 10$。 在第二个测试用例中，有 $01011\to 00101\to 11101\to 01000\to 10100\to 00100\to 11100$。 在第三个测试用例中，两个字符串已经相同。另一种方案是翻转长度为 $2$ 的前缀，这样 $a$ 不会发生变化。 由 ChatGPT 4.1 翻译