#PQJ44x5217. QOJ 44_5217
QOJ 44_5217
2 线段树 2.1 题目᧿䘠 线段树是九条可怜很喜欢的一个数据结构,它拥有着简单的结构、优秀的复杂度与强大的 功能,因此可怜曾经花了很长时间研究线段树的一些性质。 最近可怜又开始研究起线段树来了,有所不同的是,她把目光放在了更广义的线段树上: 在正常的线段树中,对于区间[l, r],我们会取m = ⌊l+r 2 ⌋,然后将这个区间分成[l, m] 和 [m + 1, r] 两个子区间。在广义的线段树中,m 不要求恰好等于区间的中点,但是m 还是必须 满足l ≤m < r 的。不难发现在广义的线段树中,树的深度可以达到O(n) 级别。 例如下面这棵树,就是一棵广义的线段树: 为了方便,我们按照先序遍历给线段树上所有的节点标号,例如在上图中,[2, 3] 的标号是 5,[4, 4] 的标号是9,不难发现在[1, n] 上建立的广义线段树,它共有着2n −1 个节点。 考虑把线段树上的定位区间操作(就是打懒标记的时候干的事情)移植到广义线段树上, 可以发现在广义的线段树上还是可以用传统的线段树上的方法定位区间的,例如在上图中,蓝 色节点和蓝色边就是在定位区间[2, 4] 时经过的点和边,最终定位到的点是[2, 3] 和[4, 4]。 如果你对线段树不熟悉,这儿给出定位区间操作形式化的定义:给出区间[l, r],找出尽可 能少的区间ӂ不相交的线段树节点,使得它们区间的并集恰好是[l, r]。 定义S[l,r] 为定位区间[l, r] 得到的点集,例如在上图中,S[2,4] = {5, 9}。定义线段树上两 个点u, v 的距离d(u, v) 为线段树上u 到v 最短路径上的边数,例如在上图中d(5, 9) = 3。 现在可怜给了你一棵[1, n] 上的广义的线段树并给了m 组询问,每组询问给出三个数 u, l, r(l ≤r),可怜想要知道∑ v∈S[l,r] d(u, v)。 2.2 输入格式 第一行输入一个整数n。 接下来一行包含n −1 个空格隔开的整数:按照标号递增的顺序,给出广义线段树上所有 非ਦ子节点的划分位置m。不难发现通过这些信息就能唯一确定一棵[1, n] 上的广义线段树。 4
接下来一行输入一个整数m。 之后m 行每行输入三个整数u, l, r(1 ≤u ≤2n −1, 1 ≤l ≤r ≤n),表示一组询问。 2.3 输出格式 对于每组询问,输出一个整数表示答案。 2.4 样例输入 10 3 1 2 9 6 4 5 7 8 3 7 6 7 18 4 5 14 5 6 2.5 样例输出 7 11 3 2.6 数据㤳ത与约定 测试点编号 n m 其他约定 1 ≤100 ≤100 无 2 ≤2 × 105 ≤20 3 ≤2 × 105 r = n 4 5 u = 1 6 7 无 8 9 10 对于100% 的数据,保证n ≥2, m ≥1。 5