P
r
o
b
l
e
m
\mathrm{Problem}
Problem
S
o
l
u
t
i
o
n
\mathrm{Solution}
Solution
我们知道，对于
(
x
1
,
y
1
)
,
(
x
1
,
y
2
)
,
(
x
2
,
y
1
)
(x1,y1),(x1,y2),(x2,y1)
(x1,y1),(x1,y2),(x2,y1)满足，那么
(
x
2
,
y
2
)
(x2,y2)
(x2,y2)也满足,我们需要通过分析前者和后者的关系来找到规律。即，如何寻求一个方法使得通过前者的标记使得后者被标记到。
我们需要通过对应的
x
2
x2
x2找到对应的
y
1
y1
y1，再从
y
1
y1
y1找到
x
1
x1
x1，
x
1
x1
x1找到
y
2
y2
y2。因此题目就转化成了一个连通性问题。那么，我们就可以对任意
(
x
,
y
)
(x,y)
(x,y)从
x
x
x到
y
y
y连边，再用并查集判断连通性。
C
o
d
e
\mathrm{Code}
Code
#include <cstdio>
#include <iostream>
using namespace std
;
const int N
= 6000;
int n
, m
, q
;
int a
[N
][N
], fa
[N
];
int read(void)
{
int s
= 0, w
= 0; char c
= getchar();
while (c
< '0' || c
> '9') w
|= c
== '-', c
= getchar();
while (c
>= '0' && c
<= '9') s
= s
*10+c
-48, c
= getchar();
return w
? -s
: s
;
}
int get(int x
) {
if (fa
[x
] == x
) return x
;
return fa
[x
] = get(fa
[x
]);
}
int main(void)
{
freopen("grid.in","r",stdin);
freopen("grid.out","w",stdout);
n
= read(), m
= read(), q
= read();
for (int i
=1;i
<=n
*2;++i
) fa
[i
] = i
;
while (m
--) fa
[get(read())] = get(read()+n
);
for (int i
=1;i
<=n
;++i
)
for (int j
=1;j
<=n
;++j
)
a
[i
][j
] = a
[i
][j
-1]+a
[i
-1][j
]-a
[i
-1][j
-1]+(get(i
)==get(j
+n
));
while (q
--) {
int x1
= read(), y1
= read(), x2
= read(), y2
= read();
printf("%d\n", a
[x2
][y2
]-a
[x1
-1][y2
]-a
[x2
][y1
-1]+a
[x1
-1][y1
-1]);
}
return 0;
}
