Prefix Flip (Hard Version)

题意翻译

有两个长度为 $n$ 的二进制字符串 $a$ 和 $b$ ，在一个操作中，选择字符串 $a$ 的一个前缀，同时反转前缀中的位（ $0$ 变成 $1$ ， $1$ 变成 $0$ ），并反转前缀中位的顺序。 对于字符串 $a=001011$ ，如果选择长度为 $3$ 的前缀，则字符串 $a$ 会先变成 $110011$ ，再变成 $011011$ 。 对于字符串 $a=011011$ ，如果选择长度为 $6$ 的前缀，则字符串 $a$ 会先变成 $100100$ ，再变成 $001011$ 。 您的任务是用最多 $2n$ 次操作将字符串 $a$ 变成字符串 $b$ 。 第一行输入一个整数 $t(1\le t\le100000)$ 表示数据组数. 接下来 $3t$ 行，每三行是一组数据。每一组数据第一行输入一个整数 $n(1\le \sum\limits n\le100000)$ ，表示字符串的长度，第二行输入二进制字符串 $a$ ，第三行输入二进制字符串 $b$ 。 对于每一组数据，输出一行表示答案。包括：一个整数 $k(0\le k\le2n)$ 表示操作数，后面包括 $k$ 个整数 $p_1,p_2,……,p_k(1\le p_i\le n)$ ， $p_i$ 表示第 $i$ 操作的前缀的长度。 第一个样例： $01\to11\to00\to10$ 。 第二个样例： $01011\to00101\to11101\to01000\to10100\to00100\to11100$ 。 第三个样例中， $a$ 和 $b$ 已经相同了。

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

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.

输入输出样例

输入样例 #1

5
2
01
10
5
01011
11100
2
01
01
10
0110011011
1000110100
1
0
1

输出样例 #1

3 1 2 1
6 5 2 5 3 1 2
0
9 4 1 2 10 4 1 2 1 5
1 1

说明

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.

题意翻译

有两个长度为 $n$ 的二进制字符串 $a$ 和 $b$ ，在一个操作中，选择字符串 $a$ 的一个前缀，同时反转前缀中的位（ $0$ 变成 $1$ ， $1$ 变成 $0$ ），并反转前缀中位的顺序。 对于字符串 $a=001011$ ，如果选择长度为 $3$ 的前缀，则字符串 $a$ 会先变成 $110011$ ，再变成 $011011$ 。 对于字符串 $a=011011$ ，如果选择长度为 $6$ 的前缀，则字符串 $a$ 会先变成 $100100$ ，再变成 $001011$ 。 您的任务是用最多 $2n$ 次操作将字符串 $a$ 变成字符串 $b$ 。 第一行输入一个整数 $t(1\le t\le100000)$ 表示数据组数. 接下来 $3t$ 行，每三行是一组数据。每一组数据第一行输入一个整数 $n(1\le \sum\limits n\le100000)$ ，表示字符串的长度，第二行输入二进制字符串 $a$ ，第三行输入二进制字符串 $b$ 。 对于每一组数据，输出一行表示答案。包括：一个整数 $k(0\le k\le2n)$ 表示操作数，后面包括 $k$ 个整数 $p_1,p_2,……,p_k(1\le p_i\le n)$ ， $p_i$ 表示第 $i$ 操作的前缀的长度。 第一个样例： $01\to11\to00\to10$ 。 第二个样例： $01011\to00101\to11101\to01000\to10100\to00100\to11100$ 。 第三个样例中， $a$ 和 $b$ 已经相同了。