简历制作专业模板_国内软件开发培训机构_百度seo推广怎么收费_淘宝站外引流推广方法

补题链接

看网上题解很少，来写一份，这题个人觉得思维难度不是特别大，难度主要在于代码准确度,首先将问题转化成 $x$ 向 $f(x)$ 连边，这一步转化应该是比较容易想到的，通过手模样例，会有类似的灵感,那么 $n$ 个点 , $n$ 条边，会构成基环树森林，因为图没有保证连通所以会有多棵基环树，并且还会有自环(虽然这是trivial的)
然后我们考虑如何计算答案,题解中给出如下条件

将第二个条件转化成实际意义就是，两个点都需要通过移动进入环内并且，二者在环内的路径之差是环长的倍数,也就是最终会落在同一点,了解完需要的条件后我们需要计算答案，对于第二种条件，我们只关心能否走进环，并且路径差是环长倍数。所以我们对于相同环的长度进行合并处理，注意到环长最多只有 $\sqrt{n}$ 种(通过 $(1+2+3+....+x)=n$ 推导出来的)，将环上的点的深度定义为 $0$ , 环外面的点的深度依次递增,统计每个环长深度小于等于 $1$ 的点有多少, 深度小于等于 $2$ 的点有多少,这样子做下去即可

有多颗基环树，我们怎么知道每个环长是多少呢?我们可以先找出环上的点，对环上的点进行 $BFS$,就可以知道环长.
那么我们如何知道深度呢,对环上的点跑 $DFS$ 即可,相信大家都会
我们如何求出深度小于等于 $d$ 的点有多少个呢?我们可以先求出对于每个环长，每个深度的点有多少个，再进行前缀和即可。

至此，所有的步骤已经清楚，我们先进行连边，同时建立反图，在正图上跑拓扑排序，找出所有环，对每个环进行深搜，求出所有环外点的深度，求出每个环长的深度数组并求前缀和，回答每个询问即可

同时，还有一些细节，如何是一整个大环，环外没有点如何，我们可以单独记录每个环长的数量，对于环内的贡献，用环长成数量即可

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#include<execution>
using namespace std;
using i64 = long long;
using i128 = __int128;constexpr int maxn = 1e5+10;
vector<int> g[maxn],rg[maxn];
vector<int> hc_dep[maxn];//对于每种环长算不超过d的点有多少,vector<int> 开桶，求前缀和
vector<int> hc;
int n,query,f[maxn],in[maxn],hc_num[maxn];
bool vis[maxn],vis2[maxn],vist[maxn];//是不是在环上，BFS有没有走过，dfs中有没有走过
bool in_tuopu[maxn];
void dfs(int x,int fa,int depth,int& hc_len){vist[x]=1;if(depth>0) hc_dep[hc_len].emplace_back(depth);for(int &y:rg[x]){//反图跑链长if(y==fa||vist[y]==1) continue;dfs(y,x,depth+1,hc_len);}
}void tuopu(int i){deque<int> q;q.push_back(i);while(!q.empty()){int x = q.front();q.pop_front();in_tuopu[x]=1;for(int &y:g[x]){in[y]--;if(in[y]==0) q.push_back(y);}}
}void bfs(int x){queue<int> que;que.emplace(x);vector<int> huan;while(!que.empty()){int x = que.front();que.pop();if(vis2[x]) continue;huan.emplace_back(x);vis2[x]=1;vist[x]=1;                  //在dfs的时候不进去环for(int &y:g[x]){if(vis[y]&&!vis2[y]){que.emplace(y);}}}int len = huan.size();hc.emplace_back(len);hc_num[len]++;for(auto &i:huan){dfs(i,0,0,len);}
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n;for(int i = 1;i<=n;++i){cin>>f[i];g[i].emplace_back(f[i]);in[f[i]]++;rg[f[i]].emplace_back(i);} for(int i = 1;i<=n;++i){if(in[i]==0&&!in_tuopu[i]){tuopu(i);}}//处理每个环的环长for(int i = 1;i<=n;++i){if(in[i]==0) continue;vis[i]=1;}for(int i = 1;i<=n;++i){if(in[i]>0&&!vist[i]) bfs(i);//环上的点并且没有经过}//处理每种环长小于d的大小   求的时候要去min(d,hc_dep[i].size())sort(hc.begin(),hc.end());hc.erase(unique(hc.begin(),hc.end()),hc.end());for(int i = 1;i<=n;++i){if(hc_dep[i].empty()) continue;vector<int> t;int mx = reduce(execution::par,hc_dep[i].begin(),hc_dep[i].end(),0,[&](int a,int b){return a>b?a:b;});t.assign(mx+2,0);for(auto &j:hc_dep[i]) t[j]++;for(int j = 1;j<t.size();++j) t[j]+=t[j-1];         //求前缀和hc_dep[i].swap(t);}cin>>query;i64 a,b;while(query--){cin>>a>>b;if(a==b){cout<<n<<"\n";continue;}if(a>b) swap(a,b);i64 cha = b-a,ans=0;for(auto &i:hc){if(cha%i) continue;if(hc_dep[i].empty()){                          //环外面没有点ans+=hc_num[i]*i;}else{int mx = hc_dep[i].size()-1;ans+=hc_dep[i][min(1LL*mx,a)]+i*hc_num[i];}}cout<<ans<<"\n";}return 0;
}/*
5
5 5 4 4 3 
4
9613 992
4626 8562
7139 448
296 401
*/