某岛

… : "…アッカリ~ン . .. . " .. .
August 1, 2012

BZOJ 1095. [ZJOI2007]Hide 捉迷藏

Brief description:

给定一棵树,每个节点要么是黑色,要么是白色,能执行两个操作:
。。。把某一个点取反色,返回距离最远的黑色点对。

Analysis:

。。。… 。。链分治和边分治的方法参见 Qtree 4 那篇。。)
。。这里记录一下括号序列的方法。。。)

定义一种对一棵树的括号编码。这种编码方式很直观,所以,这里不给出严格的定义,用以下这棵树为例:

(图片自行脑补。。。)

可以先序遍历后写成:[A[B[E][F[H][I]]][C][D[G]]]
去掉字母后的串:[[[][[][]]][][[]]]

就称为这棵树的括号编码。(这个编码本质上是由深度优先遍历得到的)
考察两个结点,如 E 和 G ,

取出介于它们之间的那段括号编码 :][[][]]][][[
把匹配的括号去掉,得到:]][[

我们看到 2 个 ] 和 2 个 [,也就是说,在树中,从 E 向上爬 2 步,再向下走 2 步就到了 G。
注意到,题目中需要的信息只有这棵树中点与点的距离,所以,贮存编码中匹配的括号是没有意义的。
因此,对于介于两个节点间的一段括号编码 S,可以用一个二元组 (a, b) 描述它,即这段编码去掉匹配括号后有 a 个 ] 和 b 个 [。
所以,对于两个点 PQ,如果介于某两点 PQ 之间编码 S 可表示为 (a, b),PQ 之间的距离就是 a+b。

也就是说,题目只需要动态维护:max{a+b | S’(a, b) 是 S 的一个子串,且 S’ 介于两个黑点之间},
这里 S 是整棵树的括号编码。我们把这个量记为 dis(s)。

现在,如果可以通过左边一半的统计信息和右边一半的统计信息,得到整段编码的统计,这道题就可以用熟悉的线段树解决了。

这需要下面的分析。

考虑对于两段括号编码 S1(a1, b1) 和 S2(a2, b2),如果它们连接起来形成 S(a, b)。
注意到 S1、S2 相连时又形成了 min{b, c} 对成对的括号,合并后它们会被抵消掉。(?..这里 b, c 应该分别是指 b1 和 a2。。。

所以:

当 a2 < b1 时第一段 [ 就被消完了,两段 ] 连在一起,例如:
] ] [ [  +  ] ] ] [ [  =  ] ] ] [ [
当 a2 >= b1 时第二段 ] 就被消完了,两段 [ 连在一起,例如:
] ] [ [ [  +  ] ] [ [  =  ] ] [ [ [ (?..反了?。。。

这样,就得到了一个十分有用的结论:

当 a2 < b1 时,(a,b) = (a1-b1+a2, b2),
当 a2 >= b1 时,(a,b) = (a1, b1-a2+b2)。

由此,又得到几个简单的推论:

(i) a+b = a1+b2+|a2-b1| = max{(a1-b1)+(a2+b2), (a1+b1)+(b2-a2)}
(ii) a-b = a1-b1+a2-b2
(iii) b-a = b2-a2+b1-a1

由 (i) 式,可以发现,要维护 dis(s),就必须对子串维护以下四个量:

right_plus:max{a+b | S’(a,b) 是 S 的一个后缀,且 S’ 紧接在一个黑点之后}
right_minus:max{a-b | S’(a,b) 是 S 的一个后缀,且 S’ 紧接在一个黑点之后}
left_plus:max{a+b | S’(a,b) 是 S 的一个前缀,且有一个黑点紧接在 S 之后}
left_minus:max{b-a | S’(a,b) 是 S 的一个前缀,且有一个黑点紧接在 S 之后}

这样,对于 S = S1 + S2,其中 S1(a, b)、S2(c, d)、S(e, f),就有

(e, f) = b < c ? (a-b+c, d) : (a, b-c+d)
dis(S) = max{dis(S1), left_minus(S2)+right_plus(S1), left_plus(S2)+right_minus(S1), dis(S2)}

那么,增加这四个参数是否就够了呢?
是的,因为:

right_plus(S) = max{right_plus(S1)-c+d, right_minus(S1)+c+d, right_plus(S2)}
right_minus(S) = max{right_minus(S1)+c-d, right_minus(S2)}           
left_plus(S) = max{left_plus(S2)-b+a, left_minus(S2)+b+a, left_plus(S1)}   
left_minus(S) = max{left_minus(S2)+b-a, left_minus(S1)}               

这样一来,就可以用线段树处理编码串了。实际实现的时候,在编码串中加进结点标号会更方便,对于底层结点,如果对应字符是一个括号或者一个白点,那 么right_plus、right_minus、left_plus、left_minus、dis 的值就都是 -maxlongint;如果对应字符是一个黑点,那么 right_plus、right_minus、left_plus、left_minus 都是 0,dis 是 -maxlongint。

现在这个题得到圆满解决,回顾这个过程,可以发现用一个串表达整棵树的信息是关键,这一“压”使得线段树这一强大工具得以利用.. .

———— 以上摘自 NOI08 冬令营论文 《数据结构的提炼与压缩》 by cqx 。。。

线段树维护括号序列(2s+- ...
链分治(2.5s+ ...
边分治。(23.0s++

External link:

http://www.lydsy.com/JudgeOnline/problem.php?id=1095
http://hi.baidu.com/wjbzbmr/blog/item/2b02ec1cda7abbfa1ad57656.html