前置知识
基环树，二分
思路
-
首先可以想到，选择集合次数应该被修改次数最多的点决定，所以题目实际要求是使最大操作次数最小。
-
经典二分模型，问题变为在每个点不超过 \(mid\) 的次修改后是否可以变为单调不降的序列。对于这个问题，考虑贪心，每个点都尽量选比前一个数大的最小值。先图论建模，对于每个值域 \(i\) 连 \(i->b_i\) ,我们发现形成一个内向基环树森林（每个点出度为 \(1\) )，然后判定问题，相当于要求每个点在这些树上走，走不超过 \(mid\) 次，能到达的比前一个数大的最小值。
-
如果快速解决上面的问题，我们发现 \(a_i\) 单调不增，所以我们可以考虑用一个 指针扫值域 。每次只用快速判断任意两点在基环树上的距离（这是好做的）。我们可以考虑，将环上任意一边 \((u,b_u)\) 切掉，然后看成一颗以 \(u\) 为根的树。对于两点 \((x,y)\)，如果在同一颗树且有祖先关系就直接 \(dep[x]-dep[y]\)（处理了环到环，树到树） ,如果要跨过断掉的边（即路径是 \(x->u->b_u->y\) ，其实就是从树到环的路径） 就是 \(dep[x]-dep[u]+1+dep[y]-dep[b_u]\) 。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10,inf=1e9+7;
int n,m,a[N],b[N],fa[N],dfn[N],js[N],siz[N],dep[N],del[N],tot;
vector<int> ve[N];
void add(int x,int y){ve[x].push_back(y);}
int find(int x)
{if(fa[x]==x)return x;else return fa[x]=find(fa[x]);
}
bool merge(int x,int y)
{int f1=find(x),f2=find(y);fa[f1]=f2;//要把父亲留在环上那个节点 if(f1==f2)return 0;return 1;
}
void dfs(int u)
{dfn[u]=++tot;for(int v:ve[u]){dep[v]=dep[u]+1;dfs(v);}js[u]=tot;
}
bool sub(int x,int y)
{return dfn[x]>=dfn[y]&&dfn[x]<=js[y];
}
int jl(int x,int y)
{int f1=find(x),f2=find(y);if(f1!=f2) return inf;if(sub(x,y))return dep[x]-dep[y];if(sub(b[del[f1]],y))return dep[x]+1+dep[b[del[f1]]]-dep[y];return inf;
}
bool check(int mid)
{int cur=1;for(int i=1;i<=n;i++){while(jl(a[i],cur)>mid&&cur<=m)cur++;if(cur>m)return 0;}return 1;
}
void solve()
{cin>>n>>m;tot=0;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++)fa[i]=i,ve[i].clear(),del[i]=dep[i]=0;for(int i=1;i<=m;i++){cin>>b[i]; if(merge(i,b[i]))add(b[i],i);//建反向边 else del[find(i)]=i; }for(int i=1;i<=m;i++){if(fa[i]==i)dfs(del[i]);}int l=0,r=m,ans=-1; //注意n,m不要乱用while(l<=r){int mid=(l+r)>>1;if(check(mid))ans=mid,r=mid-1;else l=mid+1; }cout<<ans<<'\n';return ;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--)solve();return 0;
}