QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100

# 8219. 线段树

统计

小 Y 最近学会了如何用线段树维护序列,并支持区间求和的操作。

以下给出本题中线段树的定义。该定义可能和你熟知的线段树有区别。

  • 线段树是一种有根的二叉树,其每个节点对应了序列上的一个区间 $[l,r)$,其中根节点对应 $[0,n)$。
  • 对于每个节点,若其代表的序列区间 $[l,r)$ 满足 $r-l=1$,则其为叶节点;否则存在整数 $m (l < m < r)$,满足其左儿子代表区间 $[l,m)$,右儿子代表区间 $[m,r)$。
    • 可以注意到,线段树的形态取决于每个非叶结点的划分点 $m$ 的选择。
  • 在区间求和的问题上,对于序列 $a_0,a_1,\ldots,a_{n-1}$,线段树的每个结点 $[l,r)$ 维护了 $\left(a_l+a_{l+1}+\cdots+a_{r-1}\right)$ 的值。

小 J 有一个长度为 $N$ 的数组 $A_0,A_1,\ldots,A_{N-1}$,他并不知道 $A$ 中的任何一个数,但是他有一棵线段树维护了 $A$ 的区间和。线段树由 $X_1,X_2,\ldots,X_{N-1}$ 给出,其中 $X_i$ 是线段树先序遍历的第 $i$ 个非叶结点的划分点。例如,如果 $N=5,X=[2,1,4,3]$,则线段树包含的结点的先序遍历为 $[0,5),[0,2),[0,1),[1,2),[2,5),[2,4),[2,3),[3,4),[4,5)$。

小 J 有 $M$ 个区间 $[L_1,R_1),[L_2,R_2),\ldots,[L_M,R_M)$,他想知道,在所有 $2^{2N-1}$ 个线段树结点的子集中,有多少个子集 $S$ 满足以下条件:

  • 如果已知 $S$ 中所有结点维护的值,则每个 $[L_i,R_i)$ 区间的和都能被唯一确定。

例如,如果已知 $[0,1),[1,2)$,就能确定 $[0,2)$ 的和;反过来,如果已知 $[0,1),[0,2)$,也能确定 $[1,2)$ 的和。但如果仅已知 $[0,2), [2, 4)$ 则不能确定 $[0, 3)$ 或 $[1, 2)$ 的和。

由于答案很大,你需要输出答案对 $998,244,353$ 取模后的值。

输入格式

从标准输入读入数据。

输入的第一行两个整数 $N,M$。

第二行 $N-1$ 个整数 $X_1,X_2,\cdots,X_{N-1}$。

接下来 $M$ 行,每行两个整数 $L_i,R_i$。

输出格式

输出到标准输出。

输出一行一个整数表示答案对 $998,244,353$ 取模后的值。

样例

输入

2 1
1
0 2

输出

5

解释

只有当直接知道 $[0,2)$ 的总和或同时知道 $[0,1)$ 和 $[1,2)$ 的总和时才能知道 $[0,2)$ 的总和,因此总的方案数为 $2^2+1=5$。

样例

输入

2 1
1
1 2

输出

5

样例

输入

5 2
2 1 4 3
1 3
2 5

输出

193

样例

输入

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

该组数据满足特殊性质。

子任务

对于所有测试数据,

  • $2\le N\le 2 \times 10^{5}$,
  • $1\le M\le \min\left\{\frac{N(N+1)}{2},2 \times 10^{5}\right\}$,
  • $\forall 1 \le i \le N-1, 1\le X_i\le N-1$,
  • 保证 $X_i$ 正确描述了一棵线段树,
  • $\forall 1 \le i \le M, 0\le L_i < R_i \le N$,
  • $\forall i \ne j, (L_i,R_i)\ne (L_j,R_j)$。

子任务 1(6 分):$N\le 10$。

子任务 2(18 分):$N\le 100$。

子任务 3(9 分):$N\le 500$。

子任务 4(17 分):$N\le 5\,000$。

子任务 5(10 分):$M=1$。

子任务 6(13 分):$M\le 5$。

子任务 7(7 分):$M=N,L_i=0,R_i=i$。

子任务 8(20 分):无额外限制。