额，又在神秘的地方被卡住了
怎么什么题都不会呜呜呜
题目链接。
题意
给定一张 个点 条边的有向图。
每一个点上有一个门，只有拿上了对应的钥匙才能打开这扇门，进入这个点。
所有的门互不相同， 号点上有
号点的钥匙， 构成了一个排列。
初始时你在点 ，并且已经获得了点
的钥匙，求有多少个点你可以到达，有多少个点你可以到达之后再走回点 。
对于每一个
求出答案。
。。
题解
考虑这么一个事情，当前拿到的钥匙种类数至多比到过的房间数多 ，所以每一次如果要去一个新的房间，那么这个房间的编号是固定的。
先考虑对于一个点
如何求出答案，首先把
所在的那个置换环拿出来。
定义可达结构为若干个点，使得对于任意两个点，以
为起点时，若当前在前面的点，则能走到后面的点。
定义强连通分量为若干个点，使得对于任意两个点，以
为起点时，那两个点互相可达。
显然若干个点可以组成一个强连通分量，若干个强连通分量组成一个可达结构。
那么初始时从
开始，每一步尝试能否将可达结构扩展一步，扩展结束后尽可能合并最后两个强连通分量。
的答案就是对应可达结构与强连通分量的点数，能做到 。
现在考虑做一遍跑出同一个置换环内的所有答案。还是对于每一个环分开考虑。
首先考虑断环为链，然后将这个链复制成两份，然后前面那个点的答案就是最终答案。
考虑怎么从后到前求出答案，过程大概是这样的，考虑一个个加点的过程：
- 首先新加的点自成一个可达结构与强连通分量；
- 考虑最前面的两个可达结构能否合并，不能则退出；
- 尽可能合并第一个可达结构里的强连通分量；特殊的事情是，若这个可达结构最终有多个强连通分量，则新加的点对最后一个强连通分量没有贡献，可以直接推出，否则回到第
步。
根据上面的内容，合并两个可达结构的时候，前一个可达结构一定只有一个强连通分量。
此时可以用 表示终点为
的，起点编号最大的点。
此时若两个可达结构第一个点分别是 ，则只需要满足 ，就可以合并两个可达结构。
然后是如何合并两个强连通分量的问题。
考虑加入一个点
时，对于每一个可达结构，维护所有终点编号 的，起点在这个可达结构内的边。
这样，新合并完一个可达结构，维护强连通分量时，只需要便利一遍第二个可达结构的边，进行合并。
注意到便利完之后这些边一定没用了，可以直接删掉。（其实同时，此时第一个可达结构一定没有记录任何边）
所以直接开 vector 记一下就好了，时间复杂度 。
代码
注意因为断环为链了，所以每一个点出现了两次，所以答案要和环长取 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
| #include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline ll lread()
{
ll s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
vc<int>rg[1500001];
vc<int>mem[3000001];
int pre[3000001];
int id[3000001];
int fa1[3000001];
int fa2[3000001];
bool vis[1500001];
int ans1[1500001];
int ans2[1500001];
int p[3000001];
int n,m;
inline int find(int *fa,int num)
{
if(fa[num]==num) return num;
return fa[num]=find(fa,fa[num]);
}
inline void clear()
{
for(int i=1;i<=2*n;i++) mem[i].clear(),pre[i]=0;
for(int i=1;i<=n;i++) vis[i]=0,rg[i].clear();
}
inline void run(int s)
{
vc<int>nod;
for(int i=s;!vis[i];i=p[i]) nod.push_back(i),vis[i]=1;
int len=nod.size();
for(int i=0;i<len;i++) nod.push_back(nod[i]+n);
for(int i=0;i<2*len;i++) id[nod[i]]=i+1;
for(int i=1;i<2*len;i++) p[nod[i-1]]=nod[i];
for(int i=2*len;i;i--)
{
int t=nod[i-1],tt=t>n?t-n:t;
for(int j:rg[tt])
{
if(id[j]>=i) mem[find(fa1,j)].push_back(j);
if(id[j]<=i) pre[t]=max(pre[t],id[j]);
if(id[j+n]>=i) mem[find(fa1,j+n)].push_back(j+n);
if(id[j+n]<=i) pre[t]=max(pre[t],id[j+n]);
}
while(id[find(fa1,t)]!=2*len)
{
int nx=p[find(fa1,t)];
if(pre[nx]<id[t]) break;
fa1[find(fa1,t)]=nx;
for(int u:mem[find(fa1,t)])
{
while(find(fa2,t)!=find(fa2,u)) fa2[find(fa2,t)]=p[find(fa2,t)];
}
mem[find(fa1,t)].clear();
if(find(fa1,t)!=find(fa2,t)) break;
}
if(i<=len)
{
ans1[t]=min(len,id[find(fa1,t)]-id[t]+1);
ans2[t]=min(len,id[find(fa2,t)]-id[t]+1);
}
}
for(int i=0;i<2*len;i++) id[nod[i]]=0;
}
inline void solve()
{
n=read(),m=read();
for(int i=1;i<=n;i++) p[i]=read();
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
rg[v].push_back(u);
}
for(int i=1;i<=2*n;i++) fa1[i]=fa2[i]=i;
for(int i=1;i<=n;i++) if(!vis[i]) run(i);
for(int i=1;i<=n;i++) printf("%d %d\n",ans1[i],ans2[i]);
}
int main()
{
int T=read();
while(T--) clear(),solve();
return 0;
}
|