不完全洗牌AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)You are given a positive integer $N$ and integer sequences of length $N$: $A=(A_1,A_2,\ldots,A_N)$ and $B=(B_1,B_2,\ldots,B_N)$.
给定一个正整数 $N$，以及两个长度为 $N$ 的整数序列：$A=(A_1,A_2,\ldots,A_N)$ 和 $B=(B_1,B_2,\ldots,B_N)$。AI (CI翻译)
You perform $N-1$ operations on $A$. The $i$-th operation $(1\le i\le N-1)$ is as follows:
你需要对 $A$ 进行 $N-1$ 次操作。第 $i$ 次操作 $(1\le i\le N-1)$ 如下：AI (CI翻译)
- Choose an integer
$j$satisfying$i < j \le N$, and swap the values of$A_i$and$A_j$.
- 选择一个满足
$i < j \le N$的整数$j$，交换$A_i$和$A_j$的值。
Find the maximum possible number of indices $k$ $(1\le k\le N)$ satisfying $A_k=B_k$ after $N-1$ operations.
求进行 $N-1$ 次操作后，满足 $A_k=B_k$ 的下标 $k$ $(1\le k\le N)$ 的数量的最大值。AI (CI翻译)
You are given $T$ test cases; solve each of them.
给定 $T$ 组测试数据，请分别求出每组数据的答案。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$1\le T\le 10^5$$2\le N\le 3\times 10^5$$1\le A_i,B_i\le N$- The sum of
$N$over all test cases is at most$3\times 10^5$. - All input values are integers.
$1\le T\le 10^5$$2\le N\le 3\times 10^5$$1\le A_i,B_i\le N$- 所有测试数据中的
$N$之和不超过$3\times 10^5$。 - 所有输入值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入内容从标准输入中读取，格式如下：AI (CI翻译)
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_TT
\text{case}_1
\text{case}_2
\vdots
\text{case}_TEach test case is given in the following format:
每组测试数据的格式如下：AI (CI翻译)
N
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_NN
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_NOutput
输出格式
AI (CI翻译)Output the answers for the test cases in order, separated by newlines.
按测试数据的顺序输出各组数据的答案，每个答案占一行。AI (CI翻译)
样例
3
3
1 1 2
1 2 3
5
1 2 3 4 5
5 4 3 2 1
6
1 2 1 1 2 1
1 1 1 2 2 2
2
2
5
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。