P5181 [COCI2009-2010#1] GENIJALAC

· · 题解

P5181 [COCI2009-2010#1] GENIJALAC

考虑连边 i\to a_i，这样会构成若干个环，而环的大小即为该环的循环节。

而多个环的循环节为它们的 \operatorname{lcm}，这个易证。

对于一段区间，由于初始 i,a_i 是排列，所以区间即使仅与环相交（不包含），该环的贡献也是它的大小。

于是我们记 S 为与 [C+1,n-D] 有交集的环的集合，对 S 中的环的大小取 \operatorname{lcm} 即可。 时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
#define int long long
#define fastIO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int maxn=5e5+3;
int n,A,B,C,D,nxt[maxn];
int col[maxn],c,siz[maxn];
int T=1;
int lcm(int a,int b){return a/__gcd(a,b)*b;}
int query(int x){
    if(!x) return 0;
    return (x-1)/T+1;
}
signed main(){
    fastIO;
    cin>>n>>A>>B>>C>>D;
    for(int i=1;i<=n;i++) cin>>nxt[i];
    for(int i=1;i<=n;i++){// 染色找环
        if(!col[i]){
            c++;
            for(int j=i;!col[j];j=nxt[j])
siz[col[j]=c]++;
        }
    }
    for(int i=C+1;i<=n-D;i++)
        T=lcm(T,siz[col[i]]);
    cout<<query(B)-query(A-1);
    return 0;
}