[题解]HNOI2016 day1最小公倍数

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

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

注意：路径可以不是简单路径。

$Solution$
注意到不一定是简单路径，所以我们看联通性即可
也就是说，我们找到所有 $a_i \leq a,b_i \leq b$ 的边，用并查集合并，看 $u,v$ 是否联通以及 $max(a_i),max(b_i)$ 是否恰好等于 $a,b$
考虑对边分块
我们将边按 $a_i$ 排序，询问按 $b_i$ 排序
每一个询问找到最后一个 $a_i$ 小于它的 $a$ 的边，加入那个块
我们处理第 $i$ 块内的询问
首先，对于前 $i-1$ 块的边，我们可以保证它们的 $a \leq$ 第 $i$ 块所有询问的 $a$
那么我们就对前面的边按 $b_i$ 再排序一次
然后，处理第 $i$ 块每个询问，由于询问的 $b_i$ 有序，所以以前加入的边可以不用删除，原基础上直接加
但是第 $i$ 块内 $b_i$ 无序
所有我们暴力枚举第 $i$ 块的边加入
但这部分要撤销
可撤销并查集即可
时间复杂度 $O(m \sqrt m logm + m \sqrt m log n + q \sqrt m logn)$
$Code$

#include <bits/stdc++.h>
#define ri register int
#define ll long long
using namespace std;
const int Maxn=5e4;
const int Maxm=1e5;
const int Maxk=350;
struct Edge {
    int x,y,a,b;
}e[Maxm+5];
struct Query {
    int x,y,a,b,id;
}q[Maxn+5];
vector<Query>v[Maxk+5];
int l[Maxk+5],r[Maxk+5],bel[Maxm+5],t[Maxm+5],ans[Maxn+5],n,m,Q;
static char buf[30000000],*p1=buf,*p2=buf,obuf[30000000],*p3=obuf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define putchar(x) (p3-obuf<1000000)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
template<typename item>
inline void read(register item &x)
{
    x=0;register char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
inline int mymax(int x,int y) {return x>y?x:y;}
struct UnionSet {
    Edge s[Maxm+5];
    int father[Maxn+5],size[Maxn+5],mx_a[Maxn+5],mx_b[Maxn+5],top;
    inline void init() {
        for(ri i=1;i<=n;i++) {
            father[i]=i,size[i]=1;
            mx_a[i]=mx_b[i]=-1;
        }
    }
    inline int getfather(int v) {
        return father[v]==v?v:getfather(father[v]);
    }
    inline void merge(Edge t) {
        int fx=getfather(t.x),fy=getfather(t.y);
        if(size[fx]<size[fy])swap(fx,fy);
        s[++top]=(Edge){fx,fy,mx_a[fx],mx_b[fx]};
        mx_a[fx]=mymax(mx_a[fx],t.a);
        mx_b[fx]=mymax(mx_b[fx],t.b);
        if(fx!=fy) {
            father[fy]=fx,size[fx]+=size[fy];
            mx_a[fx]=mymax(mx_a[fx],mx_a[fy]);
            mx_b[fx]=mymax(mx_b[fx],mx_b[fy]);
        }
    }
    inline void del() {
        while(top) {
            Edge t=s[top--];
            if(t.x!=t.y)size[t.x]-=size[t.y];
            father[t.y]=t.y;
            mx_a[t.x]=t.a,mx_b[t.x]=t.b;
        }
    }
}us;
inline bool cmp1(Edge a,Edge b) {
    return a.a<b.a;
}
inline bool cmp2(Query a,Query b) {
    return a.b<b.b;
}
inline bool cmp3(Edge a,Edge b) {
    return a.b<b.b;
}
int main() {
    read(n),read(m);
    for(ri i=1;i<=Maxk;i++)l[i]=(i-1)*Maxk+1,r[i]=min(m,i*Maxk);
    for(ri i=1;i<=m;i++) {
        read(e[i].x),read(e[i].y),read(e[i].a),read(e[i].b);
        bel[i]=(i-1)/Maxk+1;
    }
    sort(e+1,e+m+1,cmp1);
    for(ri i=1;i<=m;i++)t[i]=e[i].a;
    read(Q);
    for(ri i=1;i<=Q;i++) {
        read(q[i].x),read(q[i].y),read(q[i].a),read(q[i].b);
        q[i].id=i;
    }
    sort(q+1,q+Q+1,cmp2);
    for(ri i=1;i<=Q;i++) {
        int x=upper_bound(t+1,t+m+1,q[i].a)-t-1;
        v[bel[x]].push_back(q[i]);
    }
    for(ri i=1;i<=bel[m];i++) {
        us.init();
        sort(e+1,e+l[i],cmp3);
        int now=1;
        for(ri j=0;j<(int)v[i].size();j++) {
            Query t=v[i][j];
            while(now<l[i]&&e[now].b<=t.b) {
                us.merge(e[now]);
                ++now;
            }
            us.top=0;
            for(ri k=l[i];k<=r[i]&&e[k].a<=t.a;k++)
                if(e[k].b<=t.b)us.merge(e[k]);
            int fx=us.getfather(t.x),fy=us.getfather(t.y);
            if(fx==fy&&us.mx_a[fx]==t.a&&us.mx_b[fx]==t.b)ans[t.id]=1;
            us.del();
        }
    }
    for(ri i=1;i<=Q;i++) {
        if(ans[i])putchar('Y'),putchar('e'),putchar('s');
        else putchar('N'),putchar('o');
        putchar('\n');
    }
    fwrite(obuf,p3-obuf,1,stdout);
    return 0;
}