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
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
long long read()
{
long long x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
while(isdigit(c)){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int N=50000+100;
const int M=100000+100;
const int Q=1000;
struct line
{
int s,t,a,b,ans,no;
friend bool operator < (line x,line y)
{
return x.a<y.a;
}
}l[M],l2[M],q[N];
bool cmp1(line x,line y)
{
return x.a<y.a;
}
bool cmp2(line x,line y)
{
return x.b<y.b;
}
bool cmp3(line x,line y)
{
return x.no<y.no;
}
int n,m,K,block[Q];
struct SIT
{
int type,x,num1,num2;
}mstack[N];
int top;
struct UnF
{
int fa[N],size[N],MAX_a[N],MAX_b[N];
int FindFather(int x)
{
if(fa[x]==0) return x;
return FindFather(fa[x]);
}
void Merge(int x,int y,int a,int b,bool type)
{
int fa1=FindFather(x),fa2=FindFather(y);
if(size[fa1]>size[fa2])
swap(x,y),swap(fa1,fa2);
if(type==1)
mstack[++top].type=1,mstack[top].x=fa2,
mstack[top].num1=MAX_a[fa2],mstack[top].num2=MAX_b[fa2];
MAX_a[fa2]=max(max(MAX_a[fa2],MAX_a[fa1]),a);
MAX_b[fa2]=max(max(MAX_b[fa2],MAX_b[fa1]),b);
if(fa1==fa2)
return;
if(type==1)
mstack[++top].type=0,mstack[top].x=fa1,mstack[top].num1=fa2,mstack[top].num2=size[fa1];
fa[fa1]=fa2,size[fa2]+=size[fa1];
}
void Undo()
{
for(;top>0;top--)
{
if(mstack[top].type==0)
fa[mstack[top].x]=0,size[mstack[top].num1]-=mstack[top].num2;
else
MAX_a[mstack[top].x]=mstack[top].num1,
MAX_b[mstack[top].x]=mstack[top].num2;
}
}
int Query(int x,int y,int a,int b)
{
if(x==y and a==0 and b==0)
return size[FindFather(x)]!=1;
int fa=FindFather(x);
if(FindFather(x)!=FindFather(y)) return false;
if(MAX_a[fa]!=a or MAX_b[fa]!=b)
return false;
return true;
}
}unf[Q];
int main()
{
int t=clock();
n=read(),m=read();
for(int i=1;i<=m;i++)
{
l[i].s=read(),l[i].t=read(),l[i].a=read(),l[i].b=read();
l2[i]=l[i];
}
K=read();
for(int i=1;i<=K;i++)
q[i].s=read(),q[i].t=read(),q[i].a=read(),q[i].b=read(),q[i].no=i;
int size=int(sqrt(m*20)),cnt=m/size;
for(int i=0;i<=cnt;i++)
for(int j=1;j<=n;j++)
unf[i].size[j]=1;
sort(l+1,l+1+m,cmp1);
sort(l2+1,l2+1+m,cmp1);
for(int i=0;i<=m/size;i++)
block[i]=l[i*size].a;
sort(q+1,q+1+K,cmp2);
sort(l+1,l+1+m,cmp2);
int to=1;
for(int i=1;i<=K;i++)
{
for(;l[to].b<=q[i].b and to<=m;to++)
{
int begin=lower_bound(block,block+1+cnt,l[to].a)-block;
for(int j=begin;j<=cnt;j++)
unf[j].Merge(l[to].s,l[to].t,l[to].a,l[to].b,0);
}
int t=upper_bound(block,block+1+cnt,q[i].a)-block-1;
line tmp;tmp.a=block[t];
for(int j=upper_bound(l2+1,l2+1+m,tmp)-l2;j<=m and l2[j].a<=q[i].a;j++)
if(l2[j].b<=q[i].b)
unf[t].Merge(l2[j].s,l2[j].t,l2[j].a,l2[j].b,1);
q[i].ans=unf[t].Query(q[i].s,q[i].t,q[i].a,q[i].b);
unf[t].Undo();
}
sort(q+1,q+1+K,cmp3);
for(int i=1;i<=K;i++)
if(q[i].ans==1)
printf("Yes\n");
else
printf("No\n");
cerr<<clock()-t<<endl;
return 0;
}
|
接下来，我们考虑把所有询问按照b从小到大排序去一个个计算，每计算一个询问之前，把$b<=q[i].b$的边全部都对应地塞到联通快里面去(根据我们之前分块的定义，每条边说要塞入的并查集一定为从某个连通块开始一直往后到最后一个块为止)。 接下来，我们对应的去找最大的$a<=q[i].a$的连通块，然后把一些还零散在外面的边全部塞到那个连通块里面，这个连通块里面所有的边一定能保证$a<=q[i].a,b<=q[i].b$，我们只需要对应的看看$u,v$是否联通，它们所在的连通块的$max_a,max_b$是否满足要求即可。 我们每做完一个操作后，必须把之前连的零散的边给撤销掉。因此，我们这里必须用按秩合并的并查集。我们可以通过用一个栈/队列记录所有的修改操作(改fa/改max)一个一个改回去即可。 因为我们这里有$\sqrt m$个块，每次操作的零散边不超过$\sqrt m$条，因此总复杂度应该是$O(n \cdot \sqrt m)$
