#P18520. Segment Tree

Segment Tree

Segment Tree

最近,小 Y 学会了用线段树维护序列的区间和。本题使用以下线段树定义,其划分方式可能与你熟悉的线段树不同。

  • 线段树是一棵有根二叉树,每个结点对应序列上的一个左闭右开区间 [l,r)[l,r),根对应 [0,n)[0,n)。
  • 若结点对应的区间满足 r−l=1r-l=1,则它是叶子;否则选择一个整数 mm,满足 l<m<rl<m<r,其左儿子对应 [l,m)[l,m),右儿子对应 [m,r)[m,r)。
  • 线段树的形态由每个非叶子结点所选的划分点决定,并不要求从中点划分。
  • 对序列 a0,a1,…,an−1a_0,a_1,\ldots,a_{n-1},结点 [l,r)[l,r) 维护的值为 al+al+1+⋯+ar−1a_l+a_{l+1}+\cdots+a_{r-1}。

小 J 有一个长度为 NN 的数组 A0,A1,…,AN−1A_0,A_1,\ldots,A_{N-1}。他不知道其中任何一个数,但有一棵维护该数组区间和的线段树。

这棵树用 X1,X2,…,XN−1X_1,X_2,\ldots,X_{N-1} 给出,其中 XiX_i 是按先序遍历顺序遇到的第 ii 个非叶子结点的划分点。先序遍历先访问当前结点,再访问左子树,最后访问右子树。

例如,N=5N=5、X=[2,1,4,3]X=[2,1,4,3] 时,整棵树先序遍历所对应的区间依次为

$$[0,5),[0,2),[0,1),[1,2),[2,5),[2,4),[2,3),[3,4),[4,5).$$

另给出 MM 个区间 [L1,R1),…,[LM,RM)[L_1,R_1),\ldots,[L_M,R_M)。线段树共有 2N−12N-1 个结点,共有 22N−12^{2N-1} 个结点子集。请计算其中有多少个子集 SS 满足:

如果知道 SS 中所有结点维护的值,就能唯一确定每个给定区间 [Li,Ri)[L_i,R_i) 的区间和。

例如,知道 [0,1)[0,1)、[1,2)[1,2) 的和,就能求出 [0,2)[0,2) 的和;反过来,知道 [0,1)[0,1)、[0,2)[0,2) 的和,也能求出 [1,2)[1,2) 的和。但只知道 [0,2)[0,2)、[2,4)[2,4) 的和,无法确定 [0,3)[0,3) 或 [1,2)[1,2) 的和。

输出答案对 998244353998244353 取模的结果。

输入格式

第一行包含两个整数 N,MN,M,满足

$$2\le N\le2\times10^5,\qquad1\le M\le\min\left(\frac{N(N+1)}2,2\times10^5\right).$$

第二行包含 N−1N-1 个整数 X1,…,XN−1X_1,\ldots,X_{N-1},满足 1≤Xi≤N−11\le X_i\le N-1。保证它们按上述先序规则描述了一棵合法线段树。

接下来 MM 行,每行包含两个整数 Li,RiL_i,R_i,满足 0≤Li<Ri≤N0\le L_i<R_i\le N,表示左闭右开区间 [Li,Ri)[L_i,R_i)。

保证任意两个给定区间不相同,即对于 i≠ji\ne j,(Li,Ri)≠(Lj,Rj)(L_i,R_i)\ne(L_j,R_j)。输入只有一组数据。

输出格式

输出一行一个整数,表示答案对 998244353998244353 取模的结果。

原样例 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