分数: 1500 点
问题陈述
给定两个长度为正整数的序列 N, A=(A_1,A_2,\dots,A_N) 和 B=(B_1,B_2,\dots,B_N).
找到正整数序列的最小可能反转数 C=(C_1,C_2,\dots,C_N) 这样 i- 第一个元素 C_i is A_i or B_i.
解决 T 测试用例。
约束
- 1 \le T
- 1 \le N \le 5 \times 10^5
- 1 \le A_i,B_i \le \color{red}{\boldsymbol{3}}
- 总和 N 对于单个输入中的所有测试用例最多 5 \times 10^5.
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
在这里, \mathrm{case}_i 代表 i- 第一个测试用例。每个测试用例均按以下格式给出:
N A_1 A_2 \dots A_N B_1 B_2 \dots B_N
输出
打印答案。
示例输入 1
8 3 2 1 1 3 3 2 5 2 1 3 2 2 1 2 1 2 3 8 2 1 3 3 3 1 2 2 1 2 3 1 2 1 3 2 10 1 3 2 1 1 3 2 2 2 2 2 3 1 1 1 1 3 1 3 3 12 2 1 1 3 3 1 3 3 2 2 2 1 3 1 1 3 3 1 3 2 3 2 1 2 15 1 3 1 3 3 2 2 1 2 3 3 3 1 1 3 3 3 3 2 3 2 1 3 2 1 2 2 3 3 3 18 3 1 1 3 3 2 1 1 2 3 2 1 3 3 3 2 2 3 1 1 3 2 1 3 1 2 1 2 3 2 2 1 3 1 3 3 20 2 2 3 1 1 3 2 3 3 1 3 1 2 1 2 2 1 2 3 2 1 1 1 3 3 1 1 3 2 2 1 1 1 1 1 2 2 2 2 1
示例输出 1
1 0 6 6 20 9 5 17
对于第一个测试用例,最佳解决方案是 C=(2,3,2) 的反转数为 1.
对于第二个测试用例,最佳解决方案是 C=(1,1,1,2,3) 的反转数为 0.