#P16738. 排列操作

排列操作

题目描述

给定一个 1∼n1\sim n 的排列 (p1,p2,…,pn)(p_1,p_2,\ldots,p_n),以及一个长度为 nn 的序列 (c1,c2,…,cn)(c_1,c_2,\ldots,c_n)。

保证序列 cc 中至少存在两个不同的数。

一次操作如下:

  1. 选择两个下标 i,ji,j,满足 1≤i,j≤n1\le i,j\le n 且 ci≠cjc_i\ne c_j;
  2. 交换 pip_i 与 pjp_j。

求至少需要进行多少次操作,才能使得对任意 1≤i≤n1\le i\le n,均有 pi=ip_i=i。

可以证明,一定存在满足要求的操作方案。

输入格式

本题包含多组测试数据。

第一行输入一个正整数 tt,表示测试数据组数。

对于每组测试数据:

  • 第一行输入一个正整数 nn;
  • 第二行输入 nn 个正整数 p1,p2,…,pnp_1,p_2,\ldots,p_n;
  • 第三行输入 nn 个正整数 c1,c2,…,cnc_1,c_2,\ldots,c_n。

输出格式

对于每组测试数据,输出一行一个非负整数,表示最少操作次数。

样例 1

2
5
2 1 4 3 5
1 2 1 2 1
5
2 1 4 5 3
1 1 1 2 1
2
5

样例 1 解释

对于第一组数据,可以先交换 p1,p2p_1,p_2,再交换 p3,p4p_3,p_4,共进行 22 次操作。

对于第二组数据,一种最优方案是依次交换:

[ (p_4,p_5),\ (p_1,p_4),\ (p_2,p_4),\ (p_1,p_4),\ (p_3,p_4). ]

样例 2

2
8
2 1 4 3 6 5 8 7
1 1 1 1 1 1 2 2
8
2 1 4 3 6 5 8 7
1 1 2 2 3 3 4 4
10
8

数据范围与约定

对于所有测试数据:

  • 1≤t≤101\le t\le 10;
  • 2≤n≤3×1052\le n\le 3\times 10^5;
  • (p1,p2,…,pn)(p_1,p_2,\ldots,p_n) 是 1∼n1\sim n 的一个排列;
  • 1≤ci≤n1\le c_i\le n;
  • (c1,c2,…,cn)(c_1,c_2,\ldots,c_n) 中至少存在两个不同的数。
测试点编号 nn 特殊性质
1∼31\sim 3 ≤7\le 7 A
4,54,5 ≤3×105\le 3\times 10^5 B
6,76,7 A
8∼108\sim 10 无

特殊性质:

  • A:ci≤2c_i\le 2;
  • B:ci=ic_i=i。

本题输入规模较大,请使用足够快的读入方式。