题解：AT_agc060_e [AGC060E] Number of Cycles

· · 题解

[AGC060E] Number of Cycles

设 f(a) 表示排列 a 中的置换环数量，给定一个 1\sim n 的排列 p 和正整数 k，构造一个 1\sim n 的排列 x 满足 f(x)+f(x\circ p) = k。或者报告无解。

$n\le 2\times 10^5

给出一个比较简洁的 \mathcal{O}(n) 做法。

我们考虑用调整法，设 y = x\circ p，初始时设 x_i = i,y_i = a_i，每次选择 i,j 并同时交换 (x_i,x_j),(y_i,y_j)。可以发现如果交换 (x_i,x_j)，当 x_i,x_j 处于同一个环中时会分裂为两个环，否则会合并为一个环，即 f(x) 的变化量为 -1,1，y 同理。那么 f(x)+f(y) 的变化量为 -2,0,2，即奇偶性不会改变。

考虑求出 f(x)+f(y) 最大能取到多少。我们任意取一个满足 f(x)+f(y) 最大的 x，如果 x 有某一个环长度 >1，那么将这个环拆为两个环 f(x)+f(y) 一定不会减小，而因为 f(x)+f(y) 已经是最大的了所以不会改变。于是我们一直操作下去直到所有环长度为 1，即 x_i=i，此时 f(x)+f(y) = n+f(p)，也就是 f(x)+f(y) 能取到的最大值，设为 s。

那么如果 k>s 或 k 和 s 不同奇偶那么一定无解，否则一定有解，下面给出一种构造。还是考虑调整法，初始时 x_i=i,y_i=a_i，并实时维护 s，初始 s = n+f(p)。

依次枚举 y 的每个置换环，将每个环上的数依次写下来，设为序列 b。我们依次枚举 i 从 2 到 n，每次要将 x_{b_1}\sim x_{b_i} 连成一个环，同时要将 y_{b_1},\ldots,y_{b_i} 连成一个或两个环，其余位置不管。假设已经考虑完了 1\sim i-1，设 lst 表示 y 中 b_1,\ldots,b_{y-1} 里面的某个和 b_1 不在同一个环中的点，如果没有就是 0，分以下几种情况考虑：

可以发现，当 i 枚到 n 的时候 s 一定为 2 或 3，取决于 n+f(p) 的奇偶性，此时一定有 k\ge s，那么中途一定存在一个时刻满足 s=k，在这个时刻退出循环并输出答案即可。复杂度 \mathcal{O}(n)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
using namespace std;
const int N = 2e5+5;
int a[N],b[N],c[N],id[N],n,k;
char buf[1<<21],*p1,*p2;
inline int rd()
{
    char c;int f = 1;
    while(!isdigit(c = getchar()))if(c=='-')f = -1;
    int x = c-'0';
    while(isdigit(c = getchar()))x = x*10+(c^48);
    return x*f;
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    for(int t = rd();t--;)
    {
        n = rd();k = rd();int tot = 0,cnt = n,lst = 0;
        for(int i = 1;i <= n;i++)a[i] = rd(),b[i] = i,id[i] = 0;
        for(int i = 1;i <= n;i++)if(!id[i])
        {
            cnt++;
            for(int x = i;!id[x];x = a[x])c[++tot] = x,id[x] = cnt;
        }
        if(k > cnt||k%2 != cnt%2){puts("No");continue;}
        for(int i = 2;i <= n&&cnt > k;i++)
            if(id[c[i]] != id[c[i-1]])swap(b[c[1]],b[c[i]]),cnt -= 2;
            else if(lst)swap(b[lst],b[c[i]]),lst = 0,cnt -= 2;
            else lst = c[i],swap(b[c[1]],b[c[i]]);
        puts("Yes");
        for(int i = 1;i <= n;i++)printf("%d%c",b[i]," \n"[i==n]);
    }
    return 0;
}