P9150 邮箱题
Alex_Wei 做法妙。
思路
首先我们可以建出两张图，一张是按照题目的要求形成的有向图，一张是由有向边 \((i,k_i)\) 形成的钥匙图。
在钥匙图中，每个点有且仅有一入度一出度，其形成了若干个环。
考虑当前点 \(i\)，模拟题目过程不断跳点，跳出的序列为 \(a=\{i,k_i,k_{k_i},\dots,j \}\)。对于 \(k_j\) 的可到达性我们进行探究。
- \(k_j \neq i\)。
- 其次存在一个 \(p\) 使得原图中存在边 \((p\to k_j)\)，且 \(j\) 可到达 \(p\)。
如何判定条件 2 呢？由于 \(a_i\) 可到达 \(a_{i+1}\)，每次序列拓展 \(a_p=j\) 时，考虑 \(p\) 的返租边 \(a_p\to a_q(q<p)\)，则 \(a_q\) 到 \(a_p\) 之间强连通，使用并查集维护强连通块，加入 \(k_j\) 时枚举边 \(u\to k_j\) 找是否有 \(u\in a\) 且 \(u\) 与 \(j\) 强连通。
复杂度 \(O(nm\alpha)\)。
这么跑肯定会炸，发现处理环的过程中会经过大量重复的点，能否利用已经求出的点的贡献呢？
将环复制两倍，破环为链，链上前一个点的答案就是该点的答案，如果答案统计时超过了环的长度，那么答案就为环长。
设现在的链为 \(c\)，如果 \(c_{i+1}\sim c_L\) 的答案已经求出，那么钥匙图上会形成若干条链，表示链头开始可以走到链尾；原图上是若干个子图，这些子图间可能有边相连，但由于根据题目条件这两个子图互不可达，这里仍然认为是两个子图；也就是一个子图对应一条钥匙图上的链。
对子图中的强连通分量进行缩点，发现最终缩成了一条链。
下文不加特殊说明，均有以下几点约定：
-
链均指子图缩点形成的链。
-
\(c_u\to c_v\) 表示用 \(c_u\sim c_v\) 中的点形成的子图缩点后形成的链。
-
单个 \(c_u\) 仍表示一个破环为链后 \(c\) 序列的一个点。
-
\(c_i\) 视为新加入的点。
-
点 \(c_u\) 的编号为 \(u\)。
新加入点 \(c_i\) 就相当于判断 \(c_i\to c_i\) 能否和 \(c_{i+1}\to c_p\) 合并，合并之后再次判断 \(c_i\to c_p\) 能否和 \(c_{p+1}\to c_{p`}\) 合并，不断重复链合并，直到无法进行下一次合并。
对于链 \(c_i \to c_p\) 和 \(c_{p+1}\to c_{p`}\)，根据朴素做法的判断条件，找到 \(c_u\) 与 \(c_p\) 强连通且存在边 \(c_u\to c_{p+1}\)（这里是原图中的有向边），就可以合并链。
\(c_u\) 换一个角度找会更方便，找存在边 \(c_u\to c_{p+1}(u\in[i,p])\) 的最大的 \(u\)，判断 \(c_u,c_p\) 是否共一个强连通分量，因为显然如果存在 \(v<u\) 且 \(c_v,c_p\) 属于同一个强连通分量，\(c_u,c_p\) 也属于同一个强连通分量。
合并链之后，作为一条新的链首先要进行缩点，我们不可能枚举第二条链上所有的返祖边（即满足 \(i<j\) 且村子于原图的边 \(c_j\to c_i\)）。一个好的想法是，对于 \(c_i \to c_p\)，维护所有终点编号不小于 \(i\) 且未考虑过的返祖边，合并时直接暴力跑第二条链上返祖边的影响然后合并即可。
这样就结束了吗？
仔细思考合并的过程，如果 \(c_i \to c_p\) 能和 \(c_{p+1}\to c_{p`}\) 合并，一定是由于 \(c_i\) 带来的新变化使得这两条链可以合并，否则这两条链在 \(c_i\) 加入之前就合并为一条链了。
影响链合并的因素只有 \(c_u\)，所以说 \(c_i\) 的加入带来了新的可以选择的 \(c_u\)，而 \(c_u\) 与 \(c_p\) 共一个强连通分量，可以证明 \(c_i\) 与 \(c_p\) 共一个强连通分量。
这样子对于每一条链，维护编号最大还有未贡献的返祖边的节点 \(c_x\)，这些返祖边的终点 \(u\) 满足 \(u\in c\) 且 \(i\leq k(c_k=u)\)，最后把新链头 \(c_i\sim c_x\) 合并为同一个点即可。
实现时建出反边，每次用 \(c_i\) 更新后面的链即可。
CODE
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e6+5;
struct dsu
{
int f[maxn];
inline int fr(int u){return f[u]==u?u:f[u]=fr(f[u]);}
inline void merge(int x,int y){f[fr(y)]=fr(x);}
}ch,cy;
int n,m;
int k[maxn],val[maxn],pre[maxn],ans1[maxn],ans2[maxn],in[maxn],cyc[maxn];
vector<int>E[maxn];
bool vis[maxn];
inline void solve()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&k[i]);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
E[y].push_back(x);
}
for(int i=1;i<=n;i++)
{
if(vis[i]) continue;
int p=i,ct=0;
while(!in[p]) cyc[++ct]=p,in[p]=ct,p=k[p];
for(int j=ct*2;j;j--)
{
ch.f[j]=cy.f[j]=j;val[j]=pre[j]=0;
int id=cyc[j>ct?j-ct:j];
for(int it:E[id])
{
if(!in[it]) continue;
it=in[it];
if(it+ct<j) it+=ct;
if(it>j) it-=ct;
pre[j]=max(pre[j],it);
if(it<j) it+=ct;
if(it<=ct*2) val[ch.fr(it)]=max(val[ch.fr(it)],cy.fr(it));
}
while(1)
{
while(1)
{
int cyid=cy.fr(j),chid=ch.fr(j);
if(cyid<val[chid]) cy.merge(cyid+1,cyid);
else break;
}
int cyid=cy.fr(j),chid=ch.fr(j);
val[chid]=0;
if(chid==ct*2||cyid!=chid||pre[chid+1]<j) break;
ch.merge(chid+1,chid);
}
ans1[id]=min(ct,ch.fr(j)-j+1);
ans2[id]=min(ct,cy.fr(j)-j+1);
}
for(int j=1;j<=ct;j++) in[cyc[j]]=0,vis[cyc[j]]=1;
}
for(int i=1;i<=n;i++) printf("%d %d\n",ans1[i],ans2[i]);
for(int i=1;i<=n;i++) vis[i]=false,E[i].clear();
}
int main()
{
int _;
scanf("%d",&_);
while(_--) solve();
}