[BZOJ4537][Hnoi2016]最小公倍数奇怪的分块+可撤销并查集

4537: [Hnoi2016]最小公倍数

Time Limit: 40 Sec Memory Limit: 512 MB
Submit: 1474 Solved: 521
[Submit][Status][Discuss]

Description

　　给定一张N个顶点M条边的无向图(顶点编号为1,2,…,n)，每条边上带有权值。所有权值都可以分解成2^a*3^b
的形式。现在有q个询问，每次询问给定四个参数u、v、a和b，请你求出是否存在一条顶点u到v之间的路径，使得
路径依次经过的边上的权值的最小公倍数为2^a*3^b。注意：路径可以不是简单路径。下面是一些可能有用的定义
：最小公倍数：K个数a₁,a₂,…,a_k的最小公倍数是能被每个a_i整除的最小正整数。路径：路径P:P₁,P₂,…,P_k是顶
点序列，满足对于任意1<=i<k，节点P_i和P_i+1之间都有边相连。简单路径：如果路径P:P₁,P₂,…,P_k中，对于任意1
<=s≠t<=k都有Ps≠Pt，那么称路径为简单路径。

Input

　　输入文件的第一行包含两个整数N和M，分别代表图的顶点数和边数。接下来M行，每行包含四个整数u、v、a、
b代表一条顶点u和v之间、权值为2^a*3^b的边。接下来一行包含一个整数q，代表询问数。接下来q行，每行包含四
个整数u、v、a和b，代表一次询问。询问内容请参见问题描述。1<=n,q<=50000、1<=m<=100000、0<=a,b<=10^9

Output

　　对于每次询问，如果存在满足条件的路径，则输出一行Yes，否则输出一行 No（注意：第一个字母大写，其余
字母小写）。

Sample Input

4 5
1 2 1 3
1 3 1 2
1 4 2 1
2 4 3 2
3 4 2 2
5
1 4 3 3
4 2 2 3
1 3 2 2
2 3 2 2
1 3 4 4

Sample Output

Yes
Yes
Yes
No
No

HINT

Source

考虑暴力做法，对于每一个询问，暴力加入满足询问的边，然后维护联通性和maxp，maxqmaxp，maxq，如果满足条件则YesYes。
两个条件的限制似乎很难用别的数据结构优化掉，那么考虑分块，先以pp为第一关键字，qq为第二关键字排序，每$m^{0.5}$分成一块。然后把每一个询问归类到相应的块中，使得这个询问的$p$大于等于块的$p$最小值小于等于最大值。
依次扫每个块，把每个块的询问取出来。设当前的块号是$i$,那么我们把$1$到$i-1$的块里面的所有的边按$b$排序，

再把这个块内的询问按$q$排序。然后扫$1$到$i-1$的符合当前询问的边，加入并查集。对于i块内的边，只能暴力扫然后加入并查集了，注意处理完这个询问后，要撤销掉在该块内加入的边。

所以此题的并查集不能路径压缩，要用启发式合并或按秩合并，两者都是$logn$的，总的时间复杂度时$O(n^{1.5}logn)$。

将代码中的启发式换成按秩合并可AC否则TLE

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #define ll long long

 #define maxn 140105

 using namespace std;

 int read() {

     int x=,f=;char ch=getchar();

     for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-;

     for(;isdigit(ch);ch=getchar()) x=x*+ch-'';

     return x*f;

 }

 int n,m,k;

 struct data {

     int a,b,p,q,id,f;

     bool operator <(const data tmp) const{

         return p==tmp.p?q<tmp.q:p<tmp.p;

     }

 }e[maxn],ask[maxn],tmp[maxn],sta[maxn];

 int fa[maxn],sz,ma[maxn],mb[maxn],size[maxn];

 int ans[maxn];

 int find(int x) {return fa[x]==x?fa[x]:find(fa[x]);}

 int cnt=;

 void merge(int x,int y,int a,int b) {

     x=find(x),y=find(y);

     if(size[x]>size[y]) swap(x,y);

     sta[++cnt].a=x;sta[cnt].b=y;sta[cnt].p=ma[y];sta[cnt].q=mb[y];sta[cnt].f=fa[x];sta[cnt].id=size[y];

     if(x==y) {

         ma[x]=max(ma[x],a);

         mb[x]=max(mb[x],b);

     }

     else {

         fa[x]=y;

         size[y]+=size[x];

         ma[y]=max(ma[y],a);

         mb[y]=max(mb[y],b);

         ma[y]=max(ma[x],ma[y]);

         mb[y]=max(mb[x],mb[y]);

     }

 }

 bool cmp(data a,data b) {return a.q==b.q?a.p<b.p:a.q<b.q;}

 int main() {

     n=read(),m=read();

     for(int i=;i<=m;i++) {

         e[i].a=read();e[i].b=read();e[i].p=read();e[i].q=read();

     }

     sort(e+,e+m+);

     sz=sqrt(m);

     k=read();

     for(int i=;i<=k;i++) {

         ask[i].a=read(),ask[i].b=read(),ask[i].p=read(),ask[i].q=read();ask[i].id=i;

     }

     sort(ask+,ask+k+,cmp);

     for(int i=;i<=m;i+=sz) {

         int top=;

         for(int j=;j<=k;j++) if(ask[j].p>=e[i].p&&(i+sz>m||ask[j].p<e[i+sz].p)) tmp[++top]=ask[j];

         sort(e+,e+i,cmp);

         for(int j=;j<=n;j++) fa[j]=j,size[j]=,ma[j]=mb[j]=-;

         int w=;

         for(int j=;j<=top;j++) {

             for(;w<i;w++) {

                 if(e[w].q>tmp[j].q) break;

                 merge(e[w].a,e[w].b,e[w].p,e[w].q);

             }

             cnt=;

             for(int t=i;t<i+sz;t++) {

                 if(e[t].p<=tmp[j].p&&e[t].q<=tmp[j].q) merge(e[t].a,e[t].b,e[t].p,e[t].q);

             }

             int t1=find(tmp[j].a),t2=find(tmp[j].b);

             if(t1==t2&&ma[t1]==tmp[j].p&&mb[t1]==tmp[j].q) ans[tmp[j].id]=;

             while(cnt) {

                 fa[sta[cnt].a]=sta[cnt].f;

                 ma[sta[cnt].b]=sta[cnt].p;

                 mb[sta[cnt].b]=sta[cnt].q;

                 size[sta[cnt].b]=sta[cnt].id;

                 cnt--;

             }

         }

     }

     for(int i=;i<=k;i++) if(ans[i]) puts("Yes");else puts("No");

 }

巴特西

[BZOJ4537][Hnoi2016]最小公倍数奇怪的分块+可撤销并查集

4537: [Hnoi2016]最小公倍数

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章

巴特西

[BZOJ4537][Hnoi2016]最小公倍数 奇怪的分块+可撤销并查集

4537: [Hnoi2016]最小公倍数

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章

[BZOJ4537][Hnoi2016]最小公倍数奇怪的分块+可撤销并查集