#6380. 「是男人就过8题——Pony.ai」IntervalTree

内存限制:256 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: luyanaa

题目描述

区间树是我们熟悉的数据结构线段树的一个拓展,她的每个点仍然表示一个区间,但是区间的分割点不一定是中点。

类似线段树,我们能在区间树上做一些询问,我们定义询问 [l,r] 的时间复杂度为我们定位区间 [l,r] 所需要访问的点数。

更加正式的,我们定义 S[l,r] 为定位区间 [l,r] 需要访问的节点集合,一个节点 v\in S[l,r] 需要满足以下条件。

  1. v 代表的区间是 [l,r] 的子区间,但是 v 父节点不满足这个条件

  2. v 中后代至少有一个节点满足条件 1

现在给定一个 [1, n] 的区间树和 q 次询问,每次询问包含一个正整数 k , 你需要求出有多少区间的时间复杂度恰好等于 k

输入格式

输入包含多组测试数据,每组数据的第一行两个整数 n q

每组数据的第二行包含 n-1 个整数,以先序遍历的形式给出了树上每个非叶子节点的分割点,若 [l,r] 的分割点为 m , 则其左孩子为 [l,m] , 右孩子为 [m+1,r]

输出格式

对于每组询问,输出一行表示答案

样例

样例输入

6 7
5 1 3 2 4
1
2
3
4
5
6
7

样例输出

1
2
2
3
6
4
3

数据范围与提示

输入保证 l\le m< r , n, q\le 10^5 以及 k\le 10^9 , 所有数据的 \sum n \sum q 均不超过 5 \times 10^5

特别鸣谢楼天城和吉如一提供试题,数据。