【BZOJ 3551】[ONTAK2010] Peaks加强版

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3551
神犇题解:http://blog.csdn.net/popoqqq/article/details/41348785

解题报告

这题强制在线,所以不能直接上启发式合并
或者强行可持久化也可以?
不过我们有更加优美的东西:Kruskal重构树

就是按照边权排序,然后做Kruskal
如果需要加边,那么我们新建一个结点,权值设为这条边的权值
然后把原来的两个点连到这个点下面当儿子
于是任意两点之间的最大边权就是他们的LCA的权值了

对于原题来讲,我们可以先倍增到最浅的可以到达的祖先
那么这个祖先的子树就是可以到达的所有点了
考虑DFS序,问题变为区间k大,这是主席树的经典应用
于是这题就做完啦!

今天上午考试考了一道类似的题目,然而忘了这个做法
是用的线段树合并+标记永久化,虽然能A但显然不如这个优雅

【Codeforces 741D】Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

相关链接

题目传送门:http://codeforces.com/contest/741/problem/D
中文题面:https://blog.sengxian.com/solutions/cf-741d

解题报告

看起来这个串的定义非常强的样子,但仔细观察不难发现,就是出现次数为奇数的字母最多出现一个
于是我们定时一个二进制状态$f_{i,j}$表示$i$到$j$这段路径中哪些字符出现了奇数次

我们考虑在每一条合法路径的LCA处将其统计
于是就变成了子树相关问题,于是非常自然想到启发式合并

考虑从子树最大的儿子那里继承集合,其他的儿子的集合暴力加入
因为走一条边,需要异或一个值,整个集合的转移我们可以记录一个标记,然后在插入时使其生效
考虑统计的话,我们在暴力插入的时候,枚举是哪一位不同,单次查询是$O(22)$的
又因为加入是$O(1)$的,所以总的时间复杂度$O(n \log n \cdot 22)$

【日常小测】资源采集

题目大意

给定一棵$n(n \le 52501)$个点的树,初始状态下,每一结点存储的能量为$0$
树上每一个点有两个属性$v_i,l_i$分别表示这个点每单位时间产生的能量,和这个点的存储能量的上限
再给定$q(q\le52501)$个操作,每个操作有三个属性$w_i,d_i,t_i$,表示
在$t_i$的时刻,遍历在$w_i$的子树中且与$w_i$距离不超过$d_i$的点,并收集这些点的能量
一个点的能量被收集后就会清空,询问每次操作能够收集到多少能量

解题报告

先来说一说链上的情况,我们定义$last_i$为$i$号点上一次被收集的时间
我们可以把相邻的且$last_i$相同的点合并在一起,然后询问的时候用函数式线段树来回答
如果还有什么问题的话,我们可以戳这个题:市场

现在考虑树上的情况,我们先搞出DFS序,将其作为一个点的横坐标
然后我们把深度作为这个点的纵坐标,然后把这个点扔到平面上
这样单次操作就是对于一个平面上的矩形进行操作
这个是经典的$Kd-Tree$的应用,可以做到单次操作只影响到$\sqrt{n}$个结点
于是将$Kd-Tree$子树中$last_i$相同的点合在一起,打一个标记
单次操作最多增加$\sqrt n$个标记,而每一次在$Kd-Tree$上走一次就会回收一个标记
于是总的操作次数为$q\sqrt n$的
当然我们也需要用平衡树的启发式合并,或者函数式线段树来支持询问
于是总的时间复杂度为:$O(q \sqrt n \log n)$

不过众所周知,这题的暴力是$O(nq)$的
所以非递归的暴力跑得飞快,两秒的题目暴力可以卡到一秒以内
所以考完改题的时候,所有改了的人都是用的暴力……