F1. Checker for Array Shuffling（思维/构造/图论）

题目

题意：定义从数组 b b b到 a a a的伤心值为从 b b b转化到 a a a的最小交换次数，其中 b b b是 a a a的一个排列。给定数组 a a a，求数组 b b b，使得 b b b到 a a a的伤心值最大化。

参考

证明：数组 b b b到 a a a的伤心值的最大值，为 n − c n t n-cnt n−cnt，其中 c n t cnt cnt为数组 a a a的出现次数最多的元素。 我们将从 b b b到 a a a的转化过程整合为交换位置的集合 { ( l 1 , r 1 ) , ( l 2 , r 2 ) , . . . ( l m , r m ) } \{(l_1,r_1),(l_2,r_2),...(l_m,r_m)\} {(l1​,r1​),(l2​,r2​),...(lm​,rm​)}，这里 r i r_i ri​有唯一性。因为如果 s w a p ( p o s j , p o s i ) , s w a p ( p o s k , p o s i ) swap(pos_j,pos_i),swap(pos_k,pos_i) swap(posj​,posi​),swap(posk​,posi​)，我们可以将其转化为 s w a p ( p o s j , p o s k ) , s w a p ( p o s j , p o s i ) swap(pos_j,pos_k),swap(pos_j,pos_i) swap(posj​,posk​),swap(posj​,posi​)。 我们将每次交换当成一条有向边，那么从 b b b到 a a a的转化过程等价为若干个有向树(DAG)的集合，其中每个DAG的点没有重复的，且每个DAG的边数等于其点数-1（树的定义）。 由于出现次数最多的元素次数为 c n t cnt cnt，因此我们最少需要构成 c n t cnt cnt个DAG。 因此最多的交换次数=所有DAG的边数= n − c n t n-cnt n−cnt

怎么构造伤心值最大的 b b b数组呢，我们可以先排序，将每个数挪到它后边 c n t cnt cnt个位置，通过这种构图方式，我们构造了 c n t cnt cnt个DAG(下标%n相同的在同一个DAG中)，保证相同的数不会在同一个DAG中。

#include 
using namespace std;
const int maxn = 200010;

int n, cnt;
int a[maxn], b[maxn];
vector ve[maxn];
int mp[maxn];
void solve() {
	scanf("%d", &n);
	cnt = 0;
	for (int i = 0; i