给你一张
n
×
m
n\times m
n
×
m
的图。
Q
Q
Q
次询问
(
x
,
y
,
x
1
,
y
1
)
(x,y,x_1,y_1)
(
x
,
y
,
x
1
,
y
1
)
问你能否从
(
x
,
y
)
∼
(
x
1
,
y
1
)
(x,y)\sim(x_1,y_1)
(
x
,
y
)
∼
(
x
1
,
y
1
)
n
,
m
≤
500
,
Q
≤
6
e
5
n,m\leq 500,Q\leq 6e5
n
,
m
≤
5
0
0
,
Q
≤
6
e
5
S
o
l
\mathrm{Sol}
S
o
l
分治 +
d
p
\mathrm{dp}
d
p
+
b
i
t
s
e
t
\mathrm{bitset}
b
i
t
s
e
t
做法
我们考虑离线做。
考虑如何判定能走到，我们对于每一行
l
l
l
设
f
i
,
j
,
k
f_{i,j,k}
f
i
,
j
,
k
表示哪些
(
i
,
j
)
(
i
∈
[
1
,
l
]
)
(i,j)(i∈[1,l])
(
i
,
j
)
(
i
∈
[
1
,
l
]
)
能够走到
(
l
,
k
)
(l,k)
(
l
,
k
)
同时设
g
i
,
j
,
k
g_{i,j,k}
g
i
,
j
,
k
哪些
(
i
,
j
)
(
i
∈
[
l
,
n
]
)
(i,j)(i∈[l,n])
(
i
,
j
)
(
i
∈
[
l
,
n
]
)
能够走到
(
l
,
k
)
(l,k)
(
l
,
k
)
。转移很简单
我们考虑分治来优化这个枚举
l
l
l
的过程。我们以
x
x
x
坐标进行分治，每次分治一边做掉一对起点终点在两端的询问。对于那些全部在一段的询问继续分治即可。
以及我们可以把 dp 用
b
i
t
s
e
t
\mathrm{bitset}
b
i
t
s
e
t
来优化，时间复杂度
O
(
log
n
×
n
m
2
w
)
O(\log n\times \frac{nm^2}{w})
O
(
lo
g
n
×
w
n
m
2
)
