[题解]HNOI2016 day1最小公倍数

问题描述
给定一张个顶点条边的无向图（顶点编号为），每条边上带有权值。所有权值都可以分解成的形式。

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

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

注意到不一定是简单路径，所以我们看联通性即可
也就是说，我们找到所有的边，用并查集合并，看是否联通以及是否恰好等于
考虑对边分块
我们将边按排序，询问按排序
每一个询问找到最后一个小于它的的边，加入那个块
我们处理第块内的询问
首先，对于前块的边，我们可以保证它们的第块所有询问的
那么我们就对前面的边按再排序一次
然后，处理第块每个询问，由于询问的有序，所以以前加入的边可以不用删除，原基础上直接加
但是第块内无序
所有我们暴力枚举第块的边加入
但这部分要撤销
可撤销并查集即可
时间复杂度

#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;
}