bzoj 4537 最小公倍数

Posted on | Views:

分块 + 并查集.

  • 如果对于每个询问 $(u,v,a,b)$ ,我们都只加入 $a,b$ 均小于等于该询问的 $a,b$ 的边,那么答案为 $Yes$ 就等价于 $u,v$ 在同一个联通块中,并且这个连通块中有一条边的 $a$ 等于该询问的 $a$ ,有一条边的 $b$ 等于该询问的 $b$ .
  • 若只有 $a$ 这一维的限制,可以将所有边,询问按 $a$ 排序后依次处理,用并查集维护.
  • 但现在有 $a,b$ 两维的限制,而 $m$ 不是很大,考虑分块.
  • 将所有边与询问按照 $a$ 的大小分成 $\sqrt m$ 块,按顺序处理每一块.处理第 $i$ 块的时候,将第 $1\sim i-1$ 块内的边和第 $i$ 块内的询问都拿出来,按照 $b$ 从小到大排序后依次处理,并用并查集维护连通性和联通块内最大的 $a,b$ .
  • 第 $i$ 块内的边也可能产生贡献,因为它们的数量不超过 $\sqrt m$ ,所以每次遇到询问时,将这些边当中合法的加入,这个询问结束后再撤销就好了.
  • 因为要实现可撤销的并查集,所以要按秩合并,不能路径压缩.时间复杂度 $O(m\sqrt m\cdot logm)$ .

注意 $a,b$ 可能为 $0$ ,所以初始化最大值要为 $-1$ .因为这个调了一节课.

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
    int out=0,fh=1;
    char jp=getchar();
    while ((jp>'9'||jp<'0')&&jp!='-')
        jp=getchar();
    if (jp=='-')
        fh=-1,jp=getchar();
    while (jp>='0'&&jp<='9')
        out=out*10+jp-'0',jp=getchar();
    return out*fh;
}
const int MAXN=5e5+10;
struct node
{
    int u,v,a,b,id;
    int type;
}eq[MAXN],tmp[MAXN];
bool cmp1(node A,node B)
{
    return A.a<B.a || (A.a==B.a && A.type<B.type);
}
bool cmp2(node A,node B)
{
    return A.b<B.b || (A.b==B.b && A.type<B.type);
}
int ans[MAXN];
int n,m,q,BlockSize,BlockNum;
int L[MAXN],R[MAXN],lpos[MAXN],rpos[MAXN];
struct Disjoint_Set_Union
{
    int fa[MAXN],siz[MAXN],maxa[MAXN],maxb[MAXN];
    int OperationNum;
    struct Operation
    {
        int x,NewFa,sizx,Orgmaxa,Orgmaxb;
    }opt[MAXN];
    void SaveOperation(int x,int NewFa,int sizx,int Orgmaxa,int Orgmaxb)
    {
        int k=++OperationNum;
        opt[k].x=x;
        opt[k].NewFa=NewFa;
        opt[k].sizx=sizx;
        opt[k].Orgmaxa=Orgmaxa;
        opt[k].Orgmaxb=Orgmaxb;
    }
    void Undo()
    {
        while(OperationNum)
        {
            int k=OperationNum--;
            int x=opt[k].x,NewFa=opt[k].NewFa;
            int sizx=opt[k].sizx;
            int Orgmaxa=opt[k].Orgmaxa;
            int Orgmaxb=opt[k].Orgmaxb;
            if(x!=NewFa)
                siz[NewFa]-=sizx;
            fa[x]=x;
            maxa[NewFa]=Orgmaxa;
            maxb[NewFa]=Orgmaxb;
        }
    }
    void init()
    {
        OperationNum=0;
        for(int i=1;i<=n;++i)
        {
            fa[i]=i;
            siz[i]=1;
            maxa[i]=maxb[i]=-1;
        }
    }
    int Find(int x)
    {
        if(fa[x]==x)
            return x;
        return Find(fa[x]);
    }
    void addedge(int u,int v,int a,int b,bool flag)
    {
        u=Find(u),v=Find(v);
        if(u!=v)
        {
            if(siz[v]>siz[u])
                swap(u,v);
            if(flag)
                SaveOperation(v,u,siz[v],maxa[u],maxb[u]);
            siz[u]+=siz[v];
            fa[v]=u;
            maxa[u]=max(maxa[u],a);
            maxa[u]=max(maxa[u],maxa[v]);
            maxb[u]=max(maxb[u],b);
            maxb[u]=max(maxb[u],maxb[v]);
        }
        else
        {
            if(flag)
                SaveOperation(u,u,siz[u],maxa[u],maxb[u]);
            maxa[u]=max(maxa[u],a);
            maxb[u]=max(maxb[u],b);
        }
    }
    bool check(int u,int v,int a,int b)
    {
        u=Find(u),v=Find(v);
        if(u!=v)
            return false;
        if(maxa[u]!=a || maxb[u]!=b)
            return false;
        return true;
    }
}DSU;
void solve(int CurBlock)
{
    DSU.init();
    int tot=0;
    for(int i=1;i<L[CurBlock];++i)
        if(eq[i].type==1)
            tmp[++tot]=eq[i];
    for(int i=L[CurBlock];i<=R[CurBlock];++i)
        if(eq[i].type==2)
            tmp[++tot]=eq[i];
    sort(tmp+1,tmp+1+tot,cmp2);
    for(int i=1;i<=tot;++i)
    {
        if(tmp[i].type==1)
            DSU.addedge(tmp[i].u,tmp[i].v,tmp[i].a,tmp[i].b,false);
        else
        {
            if(tmp[i].id==44)
            {
                int qq=1;
            }
            for(int j=L[CurBlock];j<=R[CurBlock];++j)
                if(eq[j].type==1 && eq[j].a<=tmp[i].a && eq[j].b<=tmp[i].b)
                    DSU.addedge(eq[j].u,eq[j].v,eq[j].a,eq[j].b,true);
            ans[tmp[i].id]=DSU.check(tmp[i].u,tmp[i].v,tmp[i].a,tmp[i].b);
            DSU.Undo();
        }
    }
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;++i)
    {
        eq[i].u=read();
        eq[i].v=read();
        eq[i].a=read();
        eq[i].b=read();
        eq[i].type=1;
    }
    q=read();
    for(int i=1;i<=q;++i)
    {
        eq[i+m].u=read();
        eq[i+m].v=read();
        eq[i+m].a=read();
        eq[i+m].b=read();
        eq[i+m].id=i;
        eq[i+m].type=2;
    }
    sort(eq+1,eq+m+q+1,cmp1);
    BlockSize=sqrt(m+q);
    BlockNum=(m+q+BlockSize-1)/BlockSize;
    for(int i=1;i<=BlockNum;++i)
    {
        L[i]=R[i-1]+1;
        R[i]=L[i]+BlockSize-1;
    }
    R[BlockNum]=m+q;
    for(int i=1;i<=BlockNum;++i)
        solve(i);
    for(int i=1;i<=q;++i)
        puts(ans[i]?"Yes":"No");
    return 0;
}