UOJ Logo Universal Online Judge

UOJ

#860. 【CTS2024/WC2024】线段树

附件下载 统计

小 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) 的和。

由于答案很大,你需要输出答案对 998244353 取模后的值。

输入格式

输入的第一行包含两个整数 N,M,分别表示数组长度和区间个数。

输入的第二行包含 N1 个整数 X1,X2,,XN1

接下来 M 行,每行包含两个整数 Li,Ri,表示一个区间。

输出格式

输出一行一个整数表示答案对 998244353 取模后的值。

样例 #1

样例输入 #1

2 1
1
0 2

样例输出 #1

5

样例 #2

样例输入 #2

2 1
1 
1 2

样例输出 #2

5

样例 #3

样例输入 #3

5 2
2 1 4 3
1 3
2 5

样例输出 #3

193

样例 #4

样例输入 #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

样例输出 #4

70848

提示

样例 1 解释

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

数据范围

对于所有测试数据:

  • 2N2×105
  • 1Mmin{N(N+1)2,2×105}
  • 1iN1,1XiN1
  • 保证 Xi 正确描述了一棵线段树,
  • 1iM,0Li<RiN
  • ij,(Li,Ri)(Lj,Rj)

子任务 1(6 分):N10

子任务 2(18 分):N100

子任务 3(9 分):N500

子任务 4(17 分):N5000

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

子任务 6(13 分):M5

子任务 7(7 分):M=N,Li=0,Ri=i

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

时间限制:2s

空间限制:1024MB