jzoj 5782. 【NOIP提高A组模拟2018.8.8】 城市猎人(lca+想法)

jzoj 5782. 【NOIP提高A组模拟2018.8.8】 城市猎人(lca+想法)

Description

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

Input

第一行输入三个正整数n,m,q，其中q表示询问个数。
接下来q行，每行两个正整数x，y，表示询问城市x和城市y最早什么时候连通。

Output

输出q行，每行一个正整数，表示最早连通的天数

Sample Input

Input 1
8 3 3
2 5
3 6
4 8
Input 2
25 6 1
20 9
Input 3
9999 2222 2
1025 2405
3154 8949

Sample output

Output 1
3
1
2
Output 2
4
Output 3
1980
2160

Data Constraint

对于40%的数据，n≤ 1000，q<=100000
对于100%的数据，1 ≤ n,q≤ 100000,1<=m<=q

分析：

最直观的想法就是连边，建出一棵树，用倍增维护lca。
但连边的时间复杂度为 O(n2) O ( n 2 ) $O(n^2)$，只能拿到四十分。
观察题目的连边的条件，我们可以发现:
设 x=m−i+1 x = m − i + 1 $x=m-i+1$，那么对于每个 x x $x$，x&#x3001;2x&#x3001;3x&#x2026;&#x2026;kx(kx&#x2264;n)" role="presentation">x、2x、3x……kx(kx≤n)x、2x、3x……kx(kx≤n)$x、2x、3x……kx(kx leq n)$会连成一片。
这样每个x会产生 nx n x $frac {n}{x}$条边，所以总边数为 ∑ni=1ni≈nlogn ∑ i = 1 n n i ≈ n log ⁡ n $sum_{i=1}^{n} frac{n}{i}approx n log n$条。
那么我们可以暴力连边，枚举x，然后连边。
用并查集维护联通情况，最后建出一棵树，用倍增来处理询问
时间复杂度 O(nlogn) O ( n log ⁡ n ) $O(n log n)$

code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int n,m,q,last[N],last1[N],fa[N],f[N][20][2],d[N],deep[N];
struct node{int a,b,c;
}a[2*N];
void add(int x,int y,int z) {a[++a[0].a].a=y;a[a[0].a].b=z;a[a[0].a].c=last[x];last[x]=a[0].a;
}
int getf(int x) {if (fa[x]==x || fa[x]==0) return x;fa[x]=getf(fa[x]);return fa[x];
}
void dfs(int x,int y) {int i,j,k;if (d[0]!=1) {f[x][0][0]=d[d[0]-1];f[x][0][1]=y;} for (i=1;d[0]-(1<<i)>0;i++) {f[x][i][0]=d[d[0]-(1<<i)];f[x][i][1]=max(f[x][i-1][1],f[f[x][i-1][0]][i-1][1]);}for (i=last[x];i!=0;i=a[i].c) {if (a[i].a!=d[d[0]-1]) {d[++d[0]]=a[i].a;deep[a[i].a]=deep[x]+1;dfs(a[i].a,a[i].b);d[0]--;}}
}
int work(int x,int y) {int i;if (deep[x]<deep[y]) swap(x,y);int z=0;while (deep[x]!=deep[y]) {for (i=0;deep[f[x][i][0]]>=deep[y];i++);i--;z=max(z,f[x][i][1]);x=f[x][i][0];}while (x!=y) {for (i=0;f[x][i][0]!=f[y][i][0];i++);if (i==0) {z=max(z,max(f[x][i][1],f[y][i][1]));break;}i--;z=max(z,max(f[x][i][1],f[y][i][1]));x=f[x][i][0];y=f[y][i][0];}return z;
}
int main() {freopen("pictionary.in","r",stdin);freopen("pictionary.out","w",stdout);int i,j,k=0;scanf("%d%d%d",&n,&m,&q);for (i=1;i<=m;i++) {int t=m-i+1;for (j=1;(j+1)*t<=n;j++) {int x=j*t,y=(j+1)*t;if (getf(x)!=getf(y)) {k++;add(x,y,i);add(y,x,i);fa[getf(x)]=getf(y);}}}d[0]=d[1]=1;deep[1]=1;dfs(1,0);for (i=1;i<=q;i++) {int x,y;scanf("%d%d",&x,&y);printf("%dn",work(x,y));}
}