题解——城市猎人

题解——城市猎人

题目描述：

有 (n) 个城市，标号为 (1) 到 (n)，第 (i) 天时，若 (gcd(a,b)=m-i+1)，则标号为 (a) 的城 市和标号为 (b) 的城市会建好一条直接相连的道路，有多次询问，每次询问某两座 城市最早什么时候能联通。

大体思路：

首先解决建边问题，我们不可能去枚举每一对点，然后判断它们是否联通。

对于询问，其实我们只要找出它的一颗最小生成树即可。

所以我们枚举(gcd)，对于每一个(gcd)，我们只需要考虑(gcd)与它的倍数之间的连边即可。

考虑并查集，如果这两个点不在同一个并查集中便连边。

之后可以用树上倍增解决，但是我为了追求理论时间复杂度，就用了(LCT)。

然鹅，被(O(n log^2 n))的树上倍增吊打。。。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int w[N],val[N],ch[N][2],fa[N],rev[N],f[N];
int n,m,q,x,y,tot;
int gcd(int a,int b){return a%b==0?b:gcd(b,a%b);}
int find(int x){return f[x]==x?f[x]:f[x]=find(f[x]);}
bool wh(int x){return ch[fa[x]][1]==x;}
bool isrt(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
void rever(int x){rev[x]^=1,swap(ch[x][0],ch[x][1]);}
void update(int x){val[x]=max(max(val[ch[x][0]],val[ch[x][1]]),w[x]);}
void pushdown(int x){if (rev[x]){if (ch[x][0]) rever(ch[x][0]);if (ch[x][1]) rever(ch[x][1]);rev[x]=0;}
}
void Allpushdown(int x){if (!isrt(x)) Allpushdown(fa[x]);pushdown(x);
}
void rotate(int x){int y=fa[x],z=fa[y],c=wh(x);if (!isrt(y)) ch[z][wh(fa[x])]=x;fa[x]=z;ch[y][c]=ch[x][c^1];fa[ch[y][c]]=y;ch[x][c^1]=y;fa[y]=x;update(y),update(x);
}
void splay(int x){Allpushdown(x);for (;!isrt(x);rotate(x))if (!isrt(fa[x])) rotate(wh(x)==wh(fa[x])?fa[x]:x);
}
void access(int x){for (int y=0;x;y=x,x=fa[x]) splay(x),ch[x][1]=y,update(x);
}
void makert(int x){access(x),splay(x),rever(x);
}
void link(int x,int y){makert(x),fa[x]=y;
}
int main(){freopen("pictionary.in","r",stdin);freopen("pictionary.out","w",stdout);scanf("%d%d%d",&n,&m,&q);for (int i=1;i<=n;i++) f[i]=i;for (int i=m;i>=1;i--){if (tot==n-1) break;for (int j=1;j*i<=n;j++){if (tot==n-1) break;int f1=find(i),f2=find(i*j);if (f1!=f2){++tot;w[tot+n]=m-i+1;f[f1]=f2;link(i*j,tot+n),link(i,tot+n);if (tot==n-1) break;}}}for (int i=1;i<=q;i++){scanf("%d%d",&x,&y);makert(x),access(y),splay(y);printf("%dn",val[y]);}return 0;
}

转载于:.html