题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4537
题目分析：神题一道，一开始我YY了一下LCT，发现不可做，后来看了网上大神的做法发现是分块…… 由于2和3互质，所以我们可以看成一条边有两个属性a，b。先考虑暴力怎么做：对于一个询问(u,v,A,B)，我们将所有
a<=A,b<=B
的边(a,b)加进并查集里，且在并查集的根处维护集合里所有边的a属性的最大值，以及b属性的最大值。然后查看u和v是否在同一个集合，且集合的a的最大值是否等于A，b的最大值是否等于B。 做过类似的题目的人都知道：当一条边有两种属性的时候，我们通常要对一个属性进行排序，然后对另一个属性用数据结构之类的东西优化，以降低时间复杂度。现在我们将边按a属性从小到大排序，然后分成
m−−√
块，一块一块地进行处理。假设我们处理到某一块（第h条边~第t条边）： 1.我们先找出所有
e[h].a<=ask.A<=e[t].a
的所有询问ask。 由于这些询问的A值都大于等于第h条边的a值，它也必定大于等于第1~h-1条边的a值，所以第1~h-1条边的a值都是满足要求的，它们只需要考虑b值是否小于等于这些询问的B值就行，于是： 2.将第1~h-1条边和这些询问ask按b(B)值堆在一起排序。 然后我们按b值从小到大做。对于一条边，我们直接将它加进并查集里；对于一个询问，我们先暴力扫一遍第h~t条边（因为这些边可能也合法），如果有
a<=A,b<=B
的边，就加进并查集里，并记录下来，查询完之后按顺序撤销掉这些边再做下一个操作。注意并查集不能路径压缩，要用启发式合并。 但上述方法是无法保证时间复杂度的，因为一次询问可能在做多个块的时候被处理到（比如所有边的a值和所有询问的A值都相等）。所以要加一个小优化：如果第h,t,t+1条边的a值都相等，就不处理这个块。本质上就是在所有a值相同的边中，我们只会处理最后一条边所在的块。这样不会影响正确性，而且保证了每一个询问只会在做一个块的时候被处理到，于是时间复杂度为
O(m−−√(n+m)log(n+m))
。
using namespace std;
const
int maxn=
50010;
const
int oo=
1000000001;
struct data
{
int u,v,a,b,Time;
} e[maxn<<
1];
data ask[maxn];
data sak[maxn];
int tail=
0;
int bot[maxn
*3];
int fa[maxn];
int Size[maxn];
int ma[maxn];
int mb[maxn];
int ans[maxn];
int n,
m,
q,sm;
bool Comp1(data
x,data
y)
{
return x.a<
y.a || (
x.a==
y.a &&
x.b<
y.b );
}
int Get(
int x)
{
if (
x<=
m)
return e[
x].b;
return ask[
x-
m].b;
}
bool Comp2(
int x,
int y)
{
int p=Get(
x),
q=Get(
y);
return ( p<
q || ( p==
q &&
x<=
m &&
y>
m ) );
}
int Find(
int x)
{
if (
x==fa[
x])
return x;
return Find(fa[
x]);
}
void Add(
int x)
{
int y=Find(e[
x].u),z=Find(e[
x].v);
if (
y!=z)
{
if (Size[
y]>Size[z]) swap(
y,z);
fa[
y]=z;
Size[z]+=Size[
y];
ma[z]=max(
ma[z],
ma[
y]);
mb[z]=max(mb[z],mb[
y]);
}
ma[z]=max(
ma[z],e[
x].a);
mb[z]=max(mb[z],e[
x].b);
}
void Insert(
int x)
{
int y=Find(e[
x].u),z=Find(e[
x].v);
tail++;
if (Size[
y]>Size[z]) swap(
y,z);
sak[tail].v=z;
sak[tail].a=
ma[z];
sak[tail].b=mb[z];
if (
y==z) sak[tail].u=
0;
else
{
Size[z]+=Size[
y];
fa[
y]=z;
sak[tail].u=
y;
ma[z]=max(
ma[z],
ma[
y]);
mb[z]=max(mb[z],mb[
y]);
}
ma[z]=max(
ma[z],e[
x].a);
mb[z]=max(mb[z],e[
x].b);
}
void Delete()
{
while (tail)
{
if (sak[tail].u)
{
Size[ sak[tail].v ]-=Size[ sak[tail].u ];
fa[ sak[tail].u ]=sak[tail].u;
}
ma[ sak[tail].v ]=sak[tail].a;
mb[ sak[tail].v ]=sak[tail].b;
tail--;
}
}
int main()
{
freopen(
"4537.in",
"r",stdin);
freopen(
"4537.out",
"w",stdout);
scanf(
"%d%d",&n,&
m);
for (
int i=
1; i<=
m; i++) scanf(
"%d%d%d%d",&e[i].u,&e[i].v,&e[i].a,&e[i].b);
sort(e+
1,e+
m+
1,Comp1);
e[
m+
1].a=oo;
scanf(
"%d",&
q);
for (
int i=
1; i<=
q; i++)
scanf(
"%d%d%d%d",&ask[i].u,&ask[i].v,&ask[i].a,&ask[i].b),ask[i].Time=i;
sort(ask+
1,ask+
q+
1,Comp1);
ask[
q+
1].a=oo;
sm=(
int)floor(
sqrt( (double)
m )+
1e-
7 );
int he=
1,ta=
0;
for (
int i=
1; i<=
m; i+=sm)
{
int j=min(i+sm-
1,
m);
if ( e[i].a==e[j].a && e[j].a==e[j+
1].a )
continue;
while (ask[he].a<e[i].a) he++;
while (ask[ta+
1].a<=e[j].a) ta++;
if (he<=ta)
{
for (
int k=
1; k<i; k++) bot[k]=k;
for (
int k=he; k<=ta; k++) bot[i+k-he]=
m+k;
sort(bot+
1,bot+(i+ta-he)+
1,Comp2);
for (
int k=
1; k<=n; k++) fa[k]=k,Size[k]=
1,
ma[k]=mb[k]=-
1;
for (
int k=
1; k<=i+ta-he; k++)
if (bot[k]<=
m) Add(bot[k]);
else
{
int x=bot[k]-
m;
for (
int w=i; w<=j; w++)
if ( e[w].a<=ask[
x].a && e[w].b<=ask[
x].b ) Insert(w);
int y=Find(ask[
x].u),z=Find(ask[
x].v);
if (
y!=z ||
ma[
y]<ask[
x].a || mb[
y]<ask[
x].b ) ans[ ask[
x].Time ]=
1;
else ans[ ask[
x].Time ]=
2;
Delete();
}
}
}
for (
int i=
1; i<=
q; i++)
if (ans[i]<
2)
printf(
"No\n");
else printf(
"Yes\n");
return 0;
}
