loj2048 「HNOI2016」最小公倍数

link

题意：

给定一张$N$ $个顶点$M$条边的无向图（顶点编号为$1,2,...,n$），每条边上带有权值。所有权值都可以分解成$2^a cdot 3^b$的形式。$

现在有$q$ $个询问，每次询问给定$u,v,a,b$，请你求出是否存在一条顶点$u$到$v$之间的路径，使得路径依次经过的边上的权值的最小公倍数为$2^a cdot 3^b$？$ 路径可以不是简单路径。

$n,qleq 5 imes 10^4,mleq 10^5.$

题解：

我们用qx,qy,qa,qb表示询问中的x,y,a,b，ex,ey,ea,eb表示某条边的x,y,a,b。

如何处理一个询问？将ea,eb分别小于等于qa,qb的边连接起来，若满足qx,qy连通且$max{ea}=qa&&max{eb}=qb$，则答案为Yes，否则为No。可以用并查集维护。

多个询问怎么办呢？离线。

一个分块的思路，将a分成若干块，每次处理a在当前块范围内的询问。首先询问按照b排序，对于一个询问qa,qb，我们要找所有$ealeq qa&& ebleq qb$的边，把它们连起来。

设当前块a的范围为$[L,R)$，两种情况：

$ea<L$，将ea在$[1,L)$的边按eb排序，那么只要扫过去就行了;
$Lleq ea<R$，暴力枚举合法的边插入，然后暴力退回，用一个栈维护要退回的信息;

使用无路径压缩并查集按秩合并即可。

复杂度$mathcal{O}(sqrt{m}(n+qlog n))$。

code:

 1 #pragma GCC optimize("Ofast")
 2 #include<bits/stdc++.h>
 3 #define rep(i,x,y) for (register int i=(x);i<=(y);i++)
 4 using namespace std;
 5 char gc(){
 6     static char buf[100000],*p1=buf,*p2=buf;
 7     return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
 8 }
 9 inline int read(){
10     char ch=gc(); register int x=0;
11     for (;!isdigit(ch);ch=gc());
12     for (;isdigit(ch);ch=gc()) x=x*10+ch-48;
13     return x;
14 }
15 const int N=1e5+5;
16 int n,m,Q,blo,top,x,y,sz,a,b,fa[N],mxa[N],mxb[N],siz[N]; bool ans[N];
17 struct node{
18     int x,y,a,b,id;
19     void rd(){ x=read(),y=read(),a=read(),b=read(); }
20     node(){} node(int _x,int _y,int _a,int _b,int _id){ x=_x,y=_y,a=_a,b=_b,id=_id; }
21 }e[N],q[N],nq[N],stk[N];
22 inline void up(register int &x,register int y){ x=max(x,y); }
23 inline bool cmp_a(const node &x,const node &y){ return x.a<y.a||x.a==y.a&&x.b<y.b; }
24 inline bool cmp_b(const node &x,const node &y){ return x.b<y.b||x.b==y.b&&x.a<y.a; }
25 inline int getfa(register int x){ return x==fa[x]?x:getfa(fa[x]); }
26 inline void mer(register int x,register int y,register int a,register int b){
27     x=getfa(x),y=getfa(y);
28     if (siz[x]>siz[y]) swap(x,y);
29     stk[++top].x=x; stk[top].y=y; stk[top].a=mxa[y]; stk[top].b=mxb[y]; stk[top].id=siz[y];
30     if (x!=y) fa[x]=y,siz[y]+=siz[x],up(mxa[y],mxa[x]),up(mxb[y],mxb[x]);
31     up(mxa[y],a); up(mxb[y],b);
32 }
33 int main(){
34     n=read(),m=read();
35     rep (i,1,m) e[i].rd();
36     sort(e+1,e+1+m,cmp_a); e[m+1].a=1e9;
37     Q=read();
38     rep (i,1,Q) q[i].rd(),q[i].id=i;
39     sort(q+1,q+1+Q,cmp_b);//事先将询问按照b排序，方便之后处理
40     for (register int L=1,R,Top,blo=sqrt(2*m);L<=m;L+=blo){//按照a分为sqrt个块
41         R=min(L+blo,m+1); Top=top=0;
42         rep (i,1,n) fa[i]=i,mxa[i]=mxb[i]=-1,siz[i]=1;
43         rep (i,1,Q)//提取a在当前块的询问
44             if (e[L].a<=q[i].a&&q[i].a<e[R].a) nq[++Top]=q[i];
45         if (!Top) continue;
46         if (L>1) sort(e+1,e+L,cmp_b);//a<当前块的边按照b排序
47         for (register int i=1,j=1;i<=Top;i++){
48             for (;j<L&&e[j].b<=nq[i].b;j++)//插入a<当前块的边
49                  mer(e[j].x,e[j].y,e[j].a,e[j].b);
50             top=0;
51             rep (k,L,R)
52                 if (e[k].a<=nq[i].a&&e[k].b<=nq[i].b)//插入当前块的合法边
53                     mer(e[k].x,e[k].y,e[k].a,e[k].b);
54             x=getfa(nq[i].x),y=getfa(nq[i].y);
55             ans[nq[i].id]|=x==y&&mxa[x]==nq[i].a&&mxb[x]==nq[i].b;
56             for (;top;top--){//退回
57                 x=stk[top].x,y=stk[top].y;
58                 fa[x]=x; siz[y]=stk[top].id; 
59                 mxa[y]=stk[top].a; mxb[y]=stk[top].b;
60             }
61         }
62     }
63     rep (i,1,Q) puts(ans[i]?"Yes":"No");
64     return 0;
65 }

View Code

易错：

没错你会发现我代码里的明显卡常痕迹。。。

艰辛卡常后的我……发现一个致命的错误：“提取a在当前块的询问”这部分，必须写q[i].a<e[R].a，不能改成q[i].a<=e[R-1].a。

考虑一种极端情况，所有边和询问的a全相等，时间复杂度直接退化成$n^2$。