【HNOI2016】最小公倍数

【HNOI2016】最小公倍数

容易想到先将所有边按\(a\)排序，然后处理\(b\)。(然后我就不会了

我们按\(a\)的权值分块，处理\(a\)权值位于第\(k\)个块的询问的时候，我们先将询问按\(B\)排序，然后将\([1,k-1]\)块中所有\(b_i\leq B\)的边加入并查集中。然后在第\(k\)个块中还有一些边没有加入，我们就暴力加，然后再暴力回退就好了。

分块真是灵活啊！

代码：

#include<bits/stdc++.h>
#define ll long long
#define N 100005
#define M 100005

using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

int n,m,q;
struct edge {
    int x,y,a,b;
    bool operator <(const edge &e) const {return a<e.a;}
}e[M];
vector<edge>pre;

int d[M];
int bel[M];
const int blk=350;

bool cmp(const edge &A,const edge &B) {return A.b<B.b;}

bool ans[N];
struct query {
    int x,y,a,b;
    int id;
    query() {x=y=a=b=id=0;}
    query(int X,int Y,int A,int B,int ID) {x=X,y=Y,a=A,b=B,id=ID;}
    bool operator <(const query &a)const {return b<a.b;}
};

vector<query>Q[blk];
int f[N],mxa[N],mxb[N];
int dep[N];
int Getf(int v) {
    while(f[v]!=v) v=f[v];
    return v;
    return v==f[v]?v:f[v]=Getf(f[v]);
}

int lst[N];
void Init() {
    for(int i=1;i<=n;i++) {
        f[i]=i;
        dep[i]=0;
        mxa[i]=mxb[i]=0;
    }
}

struct ope {
    int v,a,b,d;
    ope() {v=a=b=d=0;}
    ope(int V,int A,int B,int D) {v=V,a=A,b=B,d=D;}
};

vector<ope>ret;
void Get_back() {
    while(ret.size()) {
        int v=ret.back().v,a=ret.back().a,b=ret.back().b,d=ret.back().d;
        f[v]=v,mxa[v]=a,mxb[v]=b;
        dep[v]=d;
        ret.pop_back();
    }
}

void Merge(int x,int y,int a,int b,int flag) {
    x=Getf(x),y=Getf(y);
    if(flag) {
        ret.push_back(ope(x,mxa[x],mxb[x],dep[x]));
        ret.push_back(ope(y,mxa[y],mxb[y],dep[y]));
    }
    if(x==y) {
        mxa[x]=max(mxa[x],a);
        mxb[x]=max(mxb[x],b);
        return ;
    }
    if(dep[x]>dep[y]) swap(x,y);
    f[x]=y;
    if(dep[x]==dep[y]) dep[y]++;
    mxa[y]=max(mxa[y],max(mxa[x],a));
    mxb[y]=max(mxb[y],max(mxb[x],b));
}

bool pd(int x,int y,int a,int b) {
    if(Getf(x)!=Getf(y)) return 0;
    x=Getf(x);
    return mxa[x]>=lst[a]&&mxb[x]==b;
}

void work(int k) {
    Init();
    sort(Q[k].begin(),Q[k].end());
    sort(pre.begin(),pre.end(),cmp);
    int tag=0;
    int lx=(k-1)*blk+1,rx=min(m,k*blk);
    
    for(int i=0;i<Q[k].size();i++) {
        int a=Q[k][i].a,b=Q[k][i].b;
        while(tag<pre.size()&&pre[tag].b<=b) {
            Merge(pre[tag].x,pre[tag].y,pre[tag].a,pre[tag].b,0);
            tag++;
        }
        for(int j=lx;j<=a;j++) {
            if(e[j].b<=Q[k][i].b) Merge(e[j].x,e[j].y,e[j].a,e[j].b,1);
        }
        ans[Q[k][i].id]=pd(Q[k][i].x,Q[k][i].y,a,b);
        Get_back();
    }
    
    for(int i=lx;i<=rx;i++) pre.push_back(e[i]);
}

int main() {
    n=Get(),m=Get();
    for(int i=1;i<=m;i++) {
        e[i].x=Get(),e[i].y=Get(),e[i].a=Get(),e[i].b=Get();
    }
    sort(e+1,e+1+m);
    for(int i=1;i<=m;i++) d[i]=e[i].a;
    for(int i=1;i<=m;i++) e[i].a=i;
    for(int i=1;i<=m;i++) bel[i]=(i-1)/blk+1;
    lst[1]=1;
    for(int i=2;i<=m;i++) 
        if(d[i]==d[i-1]) lst[i]=lst[i-1];
        else lst[i]=i;
    q=Get();
    int x,y,a,b;
    for(int i=1;i<=q;i++) {
        x=Get(),y=Get(),a=Get(),b=Get();
        int p=upper_bound(d+1,d+1+m,a)-d-1;
        if(p&&d[p]==a) Q[bel[p]].push_back(query(x,y,p,b,i));
    }
    
    for(int i=1;i<=bel[m];i++) work(i);
    for(int i=1;i<=q;i++) 
        (ans[i])?cout<<"Yes\n":cout<<"No\n";
    return 0;
}

【HNOI2016】最小公倍数

原文：https://www.cnblogs.com/hchhch233/p/10478018.html