分块 + 并查集启发式合并
思路很简单,就是找到所有a,b都小于等于某个询问的边然后并查集合并,维护每个集合的a,b的最大值看是否等于询问的a,b.
直接暴力显然会超时,于是考虑分块,显然分成根号n块.
先整体把边按a排序,询问先读进来后按b排序,然后对于每一块的边按b排序,然后进行并查集的合并操作
值得注意的是,由于要撤销操作(分块处理,处理完一块后要“处理作案痕迹”)故这里的并查集不能使用压缩路径,否则难以实现撤销undo操作,而只能使用并查集的启发式合并,即按秩合并(这样子的话效率似乎是均摊O(lgn)？？？)并记录操作,然后撤销即可.
PS:这题本来4s时限结果LG上一开始是1s时限卡了我几次....
又臭又长的代码如下:
/*
Programed By Harry·Shaun·Wang
2016.12.4
*/
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#define MAXN 50005
#define MAXM 100005
#define MAXQ 50005
#define union Union
using namespace std;
inline int getint()
{
int x=0;
char c=getchar();
while(c<'0' || c>'9') c=getchar();
while(c>='0' && c<='9')
{
x=x*10+c-48;
c=getchar();
}
return x;
}
struct Edge
{
int from,to;
int a,b;
int index;
Edge& input(int i)
{
from=getint(),to=getint();
a=getint(),b=getint();
index=i;
return *this;
}
};
struct Operation
{
int from,to;
int father,size;
int maxa,maxb;
};
int n,m,q,l;
Edge E[MAXM],Q[MAXQ],S[MAXN];
Operation O[MAXQ];
int f[MAXN],size[MAXN];
int maxa[MAXN],maxb[MAXN];
int top,sum;
int ans[MAXQ];
inline bool cmpa(const Edge &x,const Edge &y)
{
if(x.a!=y.a) return x.a<y.a;
else return x.b<y.b;
}
inline bool cmpb(const Edge &x,const Edge &y)
{
if(x.b!=y.b) return x.b<y.b;
else return x.a<y.a;
}
inline int max(int a,int b,int c)
{
if(a<b) a=b;
if(a<c) a=c;
return a;
}
inline int find(int x)
{
while(x!=f[x]) x=f[x];
return x;
}
inline void union(int x,int y,int a,int b)
{
x=find(x),y=find(y);
if(size[x]>size[y]) swap(x,y);
++sum;
O[sum].from=x,O[sum].to=y;
O[sum].maxa=maxa[y],O[sum].maxb=maxb[y];
O[sum].father=f[x],O[sum].size=size[y];
if(x==y)
{
maxa[x]=max(maxa[x],a);
maxb[x]=max(maxb[x],b);
return;
}
f[x]=y;
size[y]+=size[x];
maxa[y]=max(maxa[x],maxa[y],a);
maxb[y]=max(maxb[x],maxb[y],b);
}
inline void undo()
{
while(sum)
{
f[O[sum].from]=O[sum].father;
size[O[sum].to]=O[sum].size;
maxa[O[sum].to]=O[sum].maxa;
maxb[O[sum].to]=O[sum].maxb;
--sum;
}
}
int main()
{
n=getint(),m=getint();
for(int i=1; i<=m; ++i) E[i].input(i);
q=getint();
for(int i=1; i<=q; ++i) Q[i].input(i);
stable_sort(E+1,E+m+1,cmpa),stable_sort(Q+1,Q+q+1,cmpb);
l=sqrt(m);
for(int i=1; i<=m; i+=l)
{
top=0;
for(int j=1; j<=q; ++j)
if(Q[j].a>=E[i].a && (i+l>m || Q[j].a<E[i+l].a))
S[++top]=Q[j];
stable_sort(E+1,E+i,cmpb);
for(int j=1; j<=n; ++j)
{
f[j]=j;
size[j]=1;
maxa[j]=maxb[j]=-1;
}
for(int j=1,k=1; j<=top; ++j)
{
for(; k<i && E[k].b<=S[j].b; ++k)
union(E[k].from,E[k].to,E[k].a,E[k].b);
sum=0;
for(int o=i; o<i+l && o<=m; ++o)
if(E[o].a<=S[j].a && E[o].b<=S[j].b)
union(E[o].from,E[o].to,E[o].a,E[o].b);
int x=find(S[j].from),y=find(S[j].to);
ans[S[j].index]=(x==y && maxa[x]==S[j].a && maxb[x]==S[j].b);
undo();
}
}
for(int i=1; i<=q; ++i)
if(ans[i]) puts("Yes");
else puts("No");
return 0;
}
