#P18520. Segment Tree
Segment Tree
Segment Tree
最近,小 Y 学会了用线段树维护序列的区间和。本题使用以下线段树定义,其划分方式可能与你熟悉的线段树不同。
- 线段树是一棵有根二叉树,每个结点对应序列上的一个左闭右开区间 ,根对应 。
- 若结点对应的区间满足 ,则它是叶子;否则选择一个整数 ,满足 ,其左儿子对应 ,右儿子对应 。
- 线段树的形态由每个非叶子结点所选的划分点决定,并不要求从中点划分。
- 对序列 ,结点 维护的值为 。
小 J 有一个长度为 的数组 。他不知道其中任何一个数,但有一棵维护该数组区间和的线段树。
这棵树用 给出,其中 是按先序遍历顺序遇到的第 个非叶子结点的划分点。先序遍历先访问当前结点,再访问左子树,最后访问右子树。
例如,、 时,整棵树先序遍历所对应的区间依次为
$$[0,5),[0,2),[0,1),[1,2),[2,5),[2,4),[2,3),[3,4),[4,5).$$另给出 个区间 。线段树共有 个结点,共有 个结点子集。请计算其中有多少个子集 满足:
如果知道 中所有结点维护的值,就能唯一确定每个给定区间 的区间和。
例如,知道 、 的和,就能求出 的和;反过来,知道 、 的和,也能求出 的和。但只知道 、 的和,无法确定 或 的和。
输出答案对 取模的结果。
输入格式
第一行包含两个整数 ,满足
$$2\le N\le2\times10^5,\qquad1\le M\le\min\left(\frac{N(N+1)}2,2\times10^5\right).$$第二行包含 个整数 ,满足 。保证它们按上述先序规则描述了一棵合法线段树。
接下来 行,每行包含两个整数 ,满足 ,表示左闭右开区间 。
保证任意两个给定区间不相同,即对于 ,。输入只有一组数据。
输出格式
输出一行一个整数,表示答案对 取模的结果。
原样例 1
2 1
1
0 2
5
原样例 2
2 1
1
1 2
5
原样例 3
5 2
2 1 4 3
1 3
2 5
193
原样例 4
10 10
5 2 1 3 4 7 6 8 9
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
70848