UOJ Logo

NOI.AC

#74. 新星线段树

统计

新星线段树

【问题描述】

8012年,实验舱所带领的计算机算法研究所不断突破人类的极限,在未知的领域不断探索并开发出了很多新的数据结构和算法,使得计算机性能有大幅度的提高(¥#@!%¥!#随便口胡请勿当真!)比如最新创造的“新星线段树”就是一个典型的例子。 什么?你居然不知道什么是线段树,SR感到很吃惊,并向你作了如下解释:

(学过线段树的同学对下面的内容可以自行略过) 1. 线段树有一个长度N。 2. 线段树是一棵二叉树,每个节点都代表了一个闭区间 $\begin{bmatrix}l,r\end{bmatrix}$ 。 3. 我们递归定义这样一个线段树:

① 根节点代表的区间为$\begin{bmatrix}1,N\end{bmatrix}$

② 叶子节点代表的区间为$\begin{bmatrix}1,r\end{bmatrix}$,满足 $l = r$。

③ 那么对于所有非叶子节点来说$\begin{bmatrix}1,N\end{bmatrix}$,满足 l < r,并且: 设 $$mid = \lfloor \frac{l + r}{2}\rfloor $$

那么该节点的左节点代表的区间为$\begin{bmatrix}1,mid\end{bmatrix}$,右节点代表的区间为$\begin{bmatrix}mid+1,r\end{bmatrix}$。

4、 不难发现我们发现线段树有以下性质:

① 树的节点个数为 $2N - 1$。

② 树的深度不超过O($logn$)。

③ 区间定位所包含的线段树节点个数不超过O($logn$)。

什么是区间定位:

用最少的线段树上节点表示的线段去拟合这个区间,每个点有且仅在这些线段中出现一次。

比如下图,区间$\begin{bmatrix}2,5\end{bmatrix}$的区间定位出的区间个数是3,分别是$\begin{bmatrix}2,2\end{bmatrix}$,$\begin{bmatrix}3,3\end{bmatrix}$,$\begin{bmatrix}4,5\end{bmatrix}$。

我们不难证明这样的区间定位是唯一的。 t3_1.jpg

(此段不要略过)

好了,相信你已经对线段树有所了解,

新创造的线段树与传统线段树的唯一区别如下:

传统线段树非叶子节点的划分点 $mid = \lfloor \frac{l + r}{2}\rfloor $,但小R线段树的划分点$mid$是自己定的。但满足 l <= mid < r,其余条件同原来线段树。

那么不难发现如下性质:

① 该线段树的节点个数依然为 $2N-1$。

② 该线段树深度可能会超过 $ O(logn) $。

③ 该线段树区间定位所包含的线段树节点个数可能超过$ O(logn) $。但区间定位的结果依然是唯一的。

小$R$给你这样一个小$R$线段树,每次询问给定区间的区间定位个数。

【输入格式】

第一行包括两个正整数,$N$,$M$,分别表示线段树的宽以及询问次数。 以下$N-1$行以先序遍历($dfs$深搜顺序)描述一个小$R$线段树,每行一个正整数表示当前非叶子节点的mid,保证每个节点 $ l <= mid < r $。 (因为叶子节点不需要,所以在读入时走到叶子节点时回溯即可,所以共 $N-1$ 个$mid$,而且保证 1~N-1各出现一次) 而后 $M$ 行每行包括两个正整数 $l,r (1<= l <=r <=N)$, 描述一个要求区间定位的区间。

【输出格式】

行每行包括一个正整数,表示给出的询问区间在给定的线段树上的区间定位个数。

【输入样例】

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

【输出样例】

4
3
3

【样例解释】

t3_2.jpg

给定线段树样子如上图。

区间$\begin{bmatrix}3,6\end{bmatrix}$定位出的区间是$\begin{bmatrix}3,3\end{bmatrix}$,$\begin{bmatrix}4,4\end{bmatrix}$,$\begin{bmatrix}5,5\end{bmatrix}$,$\begin{bmatrix}6,6\end{bmatrix}$,共四个。

区间$\begin{bmatrix}2,7\end{bmatrix}$定位出的区间是$\begin{bmatrix}2,3\end{bmatrix}$,$\begin{bmatrix}4,4\end{bmatrix}$,$\begin{bmatrix}5,7\end{bmatrix}$,共三个。

区间$\begin{bmatrix}1,6\end{bmatrix}$定位出的区间是$\begin{bmatrix}1,4\end{bmatrix}$,$\begin{bmatrix}5,5\end{bmatrix}$,$\begin{bmatrix}6,6\end{bmatrix}$,共两个。

【数据规模】

所有测试数据范围和特点如下:

t3_3.jpg