这道题着实令人摸不着头脑,
第一眼看是数论,
第二眼发现最小公倍数没用,直接取路径$\max$就好了,考虑环。
第三眼发现环也没什么用,只要限制当前询问大于$a,b$的边不添加就好了。
但是这样是$O(qm)$的,加上一个并查集的复杂度。
想办法让复杂度下降到可以接受的范围,考虑分块离线重构。
以边的$a$大小进行分块,
这样对于在同一个块内的询问(即询问的$a$在这个块内),前面那些块的边都是可以贡献的,只需考虑$b$是否超出限制就可以了,这个可以用归并思想进行优化。
对于询问所处块的边,就要暴力来加边删边,同时用按秩合并并查集进行维护。
对于一个询问,处理时间为$\sqrt{m}~log ~m$
总的复杂度是$O(q\sqrt{m}~log ~m)$
大概这样就能过了。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#define gc getchar()
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const int N=1e5+5,M=8555;
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
template<class o>
void qw(o x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)qw(x/10);
putchar(x%10+48);
}
struct node
{
int x,y,a,b,op;
bool operator <(const node a)const{return b==a.b?op<a.op:b<a.b;}
}E[N],Q[N],s1[N],s2[N];int tim,opt[N],nx[N],lmxa[N],lmxb[N],lh[N],h[N],mxa[N],mxb[N],fa[N],ans[N];
int get(int x){return x==fa[x]?x:get(fa[x]);}
bool cmp(const node a,const node b){return a.a==b.a?a.b<b.b:a.a<b.a;}
void ins(int x,int y)//临时加边 ,未来要撤回的
{
++tim;
opt[tim]=x;nx[tim]=y;lh[tim]=h[x],lmxa[tim]=mxa[x],lmxb[tim]=mxb[x];
}
void del(int t)
{
int x=opt[t];
fa[nx[t]]=nx[t];h[x]=lh[t];mxa[x]=lmxa[t];mxb[x]=lmxb[t];
}
void merge(int x,int y,int a,int b)
{
x=get(x),y=get(y);
if(x==y)
{
ins(x,0);
mxa[x]=max(mxa[x],a);
mxb[x]=max(mxb[x],b);
return ;
}
if(h[x]<h[y])swap(x,y);
ins(x,y);fa[y]=x;
if(h[x]==h[y])++h[x];
mxa[x]=max(mxa[x],max(mxa[y],a));
mxb[x]=max(mxb[x],max(mxb[y],b));
}
int main()
{
int n,m;qr(n),qr(m);
for(int i=1;i<=m;i++)
qr(E[i].x),qr(E[i].y),qr(E[i].a),qr(E[i].b);
int q;qr(q);
for(int i=1;i<=n;i++)
qr(Q[i].x),qr(Q[i].y),qr(Q[i].a),qr(Q[i].b),Q[i].op=i;
sort(E+1,E+m+1,cmp);
sort(Q+1,Q+q+1);
int B=(int)sqrt(m),T=(m-1)/B+1;
for(int t=1;t<=T;t++)
{
int L=(t-1)*B+1,R=min(m,t*B),l1=1,r1=L-1,l2=1,r2=0,cnt=0;
for(int i=1;i<=q;i++)
if(E[L].a<=Q[i].a&&(R==m||E[R+1].a>Q[i].a))
s1[++r2]=Q[i];
while(l1<=r1&&l2<=r2)
{
if(E[l1]<s1[l2])s2[++cnt]=E[l1++];
else s2[++cnt]=s1[l2++];
}
while(l2<=r2)s2[++cnt]=s1[l2++];
for(int i=1;i<=n;i++)fa[i]=i,h[i]=1,mxa[i]=mxb[i]=-1;
for(int i=1;i<=cnt;i++)
{
int x=s2[i].x,y=s2[i].y,a=s2[i].a,b=s2[i].b;
if(s2[i].op)
{
tim=0;
for(int j=L;j<=R;j++)
{
if(E[j].a>a)break;
if(E[j].b<=b)merge(E[j].x,E[j].y,E[j].a,E[j].b);
}
x=get(x),y=get(y);
ans[s2[i].op]=(x==y)&&(mxa[x]==a)&&(mxb[x]==b);
for(int j=tim;j;j--)del(j);
}
else merge(x,y,a,b);
}
sort(E+L,E+R+1);
l1=1,r1=L-1,l2=L,r2=R,cnt=0;
while(l1<=r1&&l2<=r2)
if(E[l1]<E[l2])s1[++cnt]=E[l1++];
else s1[++cnt]=E[l2++];
while(l1<=r1)s1[++cnt]=E[l1++];
while(l2<=r2)s1[++cnt]=E[l2++];
for(int i=1;i<=R;i++)E[i]=s1[i];
}
for(int i=1;i<=q;i++)
puts(ans[i]?"Yes":"No");
return 0;
}
最后一次更新于2020-03-31
0 条评论