【BZOJ1018】【SHOI2008】堵塞的交通

因为这道题比较神,单独拿出来写

题意:给你一个2*c的图,可以加边删边,维护连通性

我->小机房众人:这题怎么做啊

小机房众人->我:LCT水题

然而并不会LCT

所以比较正常的做法就是

对于每个2*2的格子,维护内部四个点的连通性(总共6条边)

那么就可以用线段树来维护整个图的连通性

不过还有一个问题就是 有可能会有这样的情况:

1

左边的先往左走,右边的往右走再绕回来

线段树只能维护某一段区间内部的联通情况所以这样的就没法查询了

r_64:可以让左边往左走到头,右边的往右走到头再查啊

我:TMD好有道理

从小机房往回走

我->众人:我会做啦balabala往左走到头往右走到头就行啦

徐子犇:这复杂度似乎不对啊

我:好像是诶 不如我们用前缀和+二分怎么样?

【被鄙视】

我->r_64:这复杂度好像不对啊

r_64->我:你不能用线段树走么

【被鄙视】

然后就会做了

调试真的爽=-=

这也是我写的第一道线段树的题呢。。。。【不可置信

于是还是玩了玩ZKW线段树 虽说查询的时候就要左右分开搞

说点什么

您将是第一位评论人!

提醒
wpDiscuz