CF1381A2.Prefix Flip (Hard Version)

This is the hard version of the problem. The difference between the versions is the constraint on $n$ and the required number of operations. You can make hacks only if all versions of the problem are solved.

There are two binary strings $a$ and $b$ of length $n$ (a binary string is a string consisting of symbols $0$ and $1$). In an operation, you select a prefix of $a$, and simultaneously invert the bits in the prefix ($0$ changes to $1$ and $1$ changes to $0$) and reverse the order of the bits in the prefix.

For example, if $a=001011$ and you select the prefix of length $3$, it becomes $011011$. Then if you select the entire string, it becomes $001001$.

Your task is to transform the string $a$ into $b$ in at most $2n$ operations. It can be proved that it is always possible.

这是该问题的困难版本。两个版本的区别在于对 $n$ 的约束以及所需操作次数的要求。仅当该问题的所有版本均被解决时，才允许进行 hack。

给定两个长度为 $n$ 的二进制字符串 $a$ 和 $b$（二进制字符串是由字符 $0$ 和 $1$ 组成的字符串）。每次操作中，你需要选择 $a$ 的一个前缀，并同时对该前缀执行两个操作：将其中每一位取反（即 $0$ 变为 $1$，$1$ 变为 $0$），再将该前缀中所有位逆序排列。

例如，若 $a=001011$，你选择长度为 $3$ 的前缀，则 $a$ 变为 $011011$；接着若你选择整个字符串作为前缀，则 $a$ 变为 $001001$。

你的任务是在至多 $2n$ 次操作内将字符串 $a$ 变为 $b$。可以证明，这总是可行的。

The first line contains a single integer $t$ ($1\le t\le 1000$) — the number of test cases. Next $3t$ lines contain descriptions of test cases.

The first line of each test case contains a single integer $n$ ($1\le n\le 10^5$) — the length of the binary strings.

The next two lines contain two binary strings $a$ and $b$ of length $n$.

It is guaranteed that the sum of $n$ across all test cases does not exceed $10^5$.

第一行包含一个整数 $t$（$1\le t\le 1000$），表示测试用例的数量。接下来的 $3t$ 行包含各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1\le n\le 10^5$），表示二进制字符串的长度。

接下来两行分别包含两个长度为 $n$ 的二进制字符串 $a$ 和 $b$。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

For each test case, output an integer $k$ ($0\le k\le 2n$), followed by $k$ integers $p_1,\ldots,p_k$ ($1\le p_i\le n$). Here $k$ is the number of operations you use and $p_i$ is the length of the prefix you flip in the $i$-th operation.

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

In the first test case, we have $01\to 11\to 00\to 10$.

In the second test case, we have $01011\to 00101\to 11101\to 01000\to 10100\to 00100\to 11100$.

In the third test case, the strings are already the same. Another solution is to flip the prefix of length $2$, which will leave $a$ unchanged.

在第一个测试用例中，我们有 $01\to 11\to 00\to 10$。

在第二个测试用例中，我们有 $01011\to 00101\to 11101\to 01000\to 10100\to 00100\to 11100$。

在第三个测试用例中，两个字符串已经相同。另一种解法是翻转长度为 $2$ 的前缀，这将使 $a$ 保持不变。