bzoj1018

题目链接

bzoj1018

题解

真是一道可怕的线段树啊QAQ

需要在矩阵中维护一个连通性,并且做判断.

显然一般的线段树合并区间并不能解决这个问题.

考虑如何维护两点之间的连通性.

如图,一共四个点,共6种需要考虑的情况.

针对这几种情况,可以在结构体中声明6个变量,用于维护这6种信息.

luru即为left-up-right-up,可以类推.

然后暴力维护连通性就好了.

查询的时候不能直接查询两个点内联通的情况,需要左右绕然后判断,所以对于查询,需要维护4个标记QAQ

多说无益,这个题还真的是无聊啊QAQ


By:Wahacer

2018.3.14

11:27

发表评论

电子邮件地址不会被公开。 必填项已用*标注