Description

  捉迷藏 Jiajia和Wind是一对恩爱的夫妻,并且他们有很多孩子。某天,Jiajia、Wind和孩子们决定在家里玩
捉迷藏游戏。他们的家很大且构造很奇特,由N个屋子和N-1条双向走廊组成,这N-1条走廊的分布使得任意两个屋
子都互相可达。游戏是这样进行的,孩子们负责躲藏,Jiajia负责找,而Wind负责操纵这N个屋子的灯。在起初的
时候,所有的灯都没有被打开。每一次,孩子们只会躲藏在没有开灯的房间中,但是为了增加刺激性,孩子们会要
求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性,Jiajia希望知道可能的最远的两
个孩子的距离(即最远的两个关灯房间的距离)。 我们将以如下形式定义每一种操作: C(hange) i 改变第i个房
间的照明状态,若原来打开,则关闭;若原来关闭,则打开。 G(ame) 开始一次游戏,查询最远的两个关灯房间的
距离。

Input

  第一行包含一个整数N,表示房间的个数,房间将被编号为1,2,3…N的整数。接下来N-1行每行两个整数a, b,
表示房间a与房间b之间有一条走廊相连。接下来一行包含一个整数Q,表示操作次数。接着Q行,每行一个操作,如
上文所示。

Output

  对于每一个操作Game,输出一个非负整数到hide.out,表示最远的两个关灯房间的距离。若只有一个房间是关
着灯的,输出0;若所有房间的灯都开着,输出-1。

Sample Input

8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
7
G
C 1
G
C 2
G
C 1
G

Sample Output

4
3
3
4

HINT

对于100%的数据, N ≤100000, M ≤500000。

括号序列的这个方法real神奇

按照深搜序我进这个之前来一个左括号 出这个的时候来个右括号 那么我们最后把这个括号序列生成出来 中间如果匹配就消去 那么这个括号序列最长的部分就是我想要的答案 因为一个括号匹配了就代表这进去将是一个子树 不可能是简单路径 此外感谢zhx巨佬给予的讲解 要不然是不可能理解这题的orz 那么这个怎么维护 我需要存放七个值 分别代表什么 a,b代表这个序列里右括号和左括号的数量 那么以后就用a,b来代替了dis就是我当前这个序列里最长的是多少 lplus就是左起a+b的最大值rplus是右起a+b的最大值 同理lminus是左起b-a的最大值 rminus是右起a-b的最大值  然后像线段树合并一样 分别讨论一下这个最大值是如何维护的 然后这些值都是怎么更新得到的 并且注意有可能不存在点或者只有一个点那么分别输出-1和0怎么搞  我是每个节点记录个size然后每次都update一下 这就可能造成蒟蒻我常数巨大 还有就是这个位置不是(x-1)*3+2因为这个括号序列匹配不确定..我后来选择记录一个Pos数组来搞定

BZOJ 1095. [ZJOI2007]Hide 捉迷藏

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

(图片自行脑补。。。)

就称为这棵树的括号编码。(这个编码本质上是由深度优先遍历得到的)
考察两个结点,如 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。。。

所以:

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

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

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

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

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

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

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

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

以上来自岛娘的blog

动态点分治 顾名思义 就是动态的.. 假如这题不需要有修改操作 那我是不是一遍朴素的点分就可以搞定了 但是现在存在修改怎么办 动态点分的操作就是我首先一遍点分把所有的重心提早找出 然后针对每一个重心的节点我像线段树一样串联起来 这样最多有log层 并且呢 为了统计 我在每个节点上暴力的使用一个数据结构 堆/multiset 来保证我的复杂度 变成n*(logn)^2的 我开设b[x]表示我x分治的这个区域中 所有子树包括自己到我上一层分治点的距离 维护一个大根堆 c[x]表示我x分治区域的这个子树中的每个点到我x节点的上一个分治节点的距离 那么同样也是维护一个大根堆 即可 这个再开设一个A表示全局的最大值 全局最大值都由什么什么构成 那显然就是每个B里面我去选一个最大和次大组合起来啊 但是堆需要删除操作 所以一个小trick 一个堆打标记一个堆加入  或者直接使用Multiset但是效率上会低一点另外为了优化常数还可以使用rmq的lca

代码有些丑陋 因为multiset的用法和priority_queue的用法我都放在一起了turn_on1&turn_off1是multi set的 bzoj大概十多秒吧 用堆的方法就比较快了 turn_on turn_off是堆来维护的

可以自行选择是使用那个此外求lca的方法也是两种lca1是rmq的方法 lca就是普通的倍增

rmq的lca怎么搞 首先遍历一遍整棵树 然后一进一出针对每条边记录两次 一共获得2*n-1个点 先按照顺序把他们依次填入mn数组 然后记录下在mn数组中对应的位置

(注意开数组的时候二倍 预处理log数组的时候也需要预处理两倍的  然后我利用动态规划的思想去搞

设mn[i][j]表示i起始长度为2^j 表示这一段深度最浅的点是谁那么 询问u,v的时候直接返回这两个区间中深度最小的点是谁 即使可能包括u的子树的节点也无妨 因为深度最浅的一定是他们的lca

一开始lca倍增写的有问题 找错足足找了很久orz菜死  然后想办法 怎么去生成一个树然后翻了很久终于找到一个可用的代码 可以生成一棵树 用的是prufer编码 如何生成一棵树 即树的数据生成器

怎么搞 首先先随机一个prufer含有n-2个元素 然后再生成一个集合1~n那么每次我去找一下最小的那个没有在prufer序列中出现的数 把他们连起来 然后在prufer序列中删掉他们重复以上步骤 然后再把最后的两个点连起来即可 对于代码中的做法 就是首先我给每个点度为1  然后随机一个prufer序列把序列里的点的度都+1 然后先按照度排序找到第一个不为0的点 输出prufer序列中的值和我的编号 然后把我的度-1  prufer序列中那个数也-1 程序中我现在固定枚举prufer编码了那么我肯定需要找啊一个不存在这里的数和当前的prufer编码连接 然后把这个删掉 原数列中的度也-1说明现在可以出现在prufer编码中了 因为原来的已经被我删掉了 这个非0就是为了防止重复利用

 

 


elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论