感觉这个题目还是非常好的。

题目中限制最小公倍数是\(2^{a}3^{b}\)

如果限制是\(2^a\), 那么是非常容易做的。

然后就可以联想一波, 得到分块的做法(≧▽≦)啦。

传送门

题目大意

多次询问是否存在\(u,v\)间的简单路径使得最小公倍数是\(2^a3^b\).

解题报告

如果最小公倍数的形式是\(2^a\), 那就可以排序+并查集直接解决。

现在是\((a,b)\)的形式, 相当于从一维拓展到两维。

如果固定住其中一维, 那么第二维的情况可以使用一维的做法解决, 但是这样做的复杂度是\(O(m^2\log m)\)的。

发现复杂度糟糕的原因是, 第一维每一次改变, 所有边都要按照第二维的顺序重新加入。

如果第一维不是每次改变都重构, 而是每跳动一个块的大小一重构, 那么复杂度是\(O(\sqrt{m}*m \log{m})\),

然后每次询问的时候, 需要把整块之外零散的边加入, 边的数量是\(\sqrt{m}\)的。

因为需要加入再撤消, 所以不能使用路径压缩的并查集, 需要启发式合并一波。

总复杂度是\(O(\sqrt{m}*m \log m * \log n + Q \sqrt{m} \log n)\)

这种复杂度都能过题?

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
#define rep(i,a,b) for(int i=int(a),nn=int(b);i<=nn;++i)
#define vep(i,a,b) for(int i=int(a),nn=int(b);i>=nn;--i)
#define xep(i,b) for(int i=0,nn=int(b);i<nn;++i)
#define x first
#define y second
#define pb push_back
#define mp make_pair
const int N=50100;
inline void in(int &x) {
char c=getchar(); int f=1;
for (;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:f);
for (x=0;c>='0'&&c<='9';c=getchar()) x=x*10+c-48;
x*=f;
}
struct info {
int u,v,a,b; info(){}
info(int u,int v,int a,int b) :u(u),v(v),a(a),b(b){}
void read() { in(u),in(v),in(a),in(b); }
} e[N<<1], qs[N<<1];
struct old {
int x,f,sz,a,b; old(){}
old(int x,int f,int sz,int a,int b)
:x(x), f(f), sz(sz), a(a),b(b) {}
};
int n,m,Q,bb;
int f[N],sz[N],ma[N],mb[N]; bool as[N];
inline bool cmpa(info a, info b) { return a.a<b.a;}
inline bool cmpe(int a,int b) { return e[a].b<e[b].b;}
inline bool cmpqs(int a,int b) { return qs[a].b<qs[b].b;}
inline void cmx(int &x,int a) { x=(a>x?a:x); }
inline void cmn(int &x,int a) { x=(a<x?a:x); }
vector<old> v;
int find(int x) { return (f[x]==x?x:find(f[x]));}
inline void merge(info e, bool tp) {
int a=find(e.u), b=find(e.v);
if (sz[a]>sz[b]) swap(a,b);
if (tp) {
v.pb(old(a,a,sz[a],ma[a],mb[a]));
v.pb(old(b,b,sz[b],ma[b],mb[b]));
}
if (a!=b) {
if (sz[a]==sz[b]) ++sz[b];
f[a]=b, cmx(ma[b],ma[a]), cmx(mb[b],mb[a]);
}
cmx(ma[b],e.a), cmx(mb[b],e.b);
}
inline void recons() {
old no; int x;
vep(i,(int)v.size()-1, 0)
no=v[i], x=v[i].x, f[x]=v[i].f, sz[x]=v[i].sz, ma[x]=v[i].a, mb[x]=v[i].b;
v.clear();
}
int main() {
static int a[N<<1],b[N<<1],fa,fb;
in(n),in(m); rep(i,1,m) e[i].read(),a[i]=i;
sort(e+1,e+1+m,cmpa); bb=sqrt(m);
in(Q); rep(i,1,Q) qs[i].read();
for (int i=0; i<=m; i+=bb) {
int hs=0;
rep(j,1,Q) if (qs[j].a>=e[i].a&&(i+bb>m||qs[j].a<e[i+bb].a))
b[++hs]=j;
if (hs==0) continue;
sort(a+1,a+i+1,cmpe);
sort(b+1,b+1+hs,cmpqs);
rep(j,1,n) f[j]=j,sz[j]=1,ma[j]=-1,mb[j]=-1;
int j=1; rep(k,1,hs) {
while (j<=i&&e[a[j]].b<=qs[b[k]].b)
merge(e[a[j]],0),++j;
rep(l,i+1,min(i+bb,m))
if (e[a[l]].a<=qs[b[k]].a) {
if (e[a[l]].b<=qs[b[k]].b) merge(e[a[l]],1);
} else break;
fa=find(qs[b[k]].u), fb=find(qs[b[k]].v);
as[b[k]]=(fa==fb&&ma[fa]==qs[b[k]].a&&mb[fa]==qs[b[k]].b);
recons();
}
}
rep(i,1,Q) puts((as[i]?"Yes":"No"));
return 0;
}

留言