QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100
[+16]

# 8219. 线段树

Statistics

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

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

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

小 J 有一个长度为 N 的数组 A0,A1,,AN1,他并不知道 A 中的任何一个数,但是他有一棵线段树维护了 A 的区间和。线段树由 X1,X2,,XN1 给出,其中 Xi 是线段树先序遍历的第 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 个区间 [L1,R1),[L2,R2),,[LM,RM),他想知道,在所有 22N1 个线段树结点的子集中,有多少个子集 S 满足以下条件:

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

例如,如果已知 [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

第二行 N1 个整数 X1,X2,,XN1

接下来 M 行,每行两个整数 Li,Ri

输出格式

输出到标准输出。

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

样例

输入

2 1
1
0 2

输出

5

解释

只有当直接知道 [0,2) 的总和或同时知道 [0,1)[1,2) 的总和时才能知道 [0,2) 的总和,因此总的方案数为 22+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

该组数据满足特殊性质。

子任务

对于所有测试数据,

  • 2N2×105
  • 1Mmin
  • \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 分):无额外限制。