#P10145. [WC2024] 线段树

[WC2024] 线段树

题目描述

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

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

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

小 J 有一个长度为 NN 的数组 A0,A1,,AN1A_0, A_1, \dots , A_{N-1},他并不知道 AA 中的任何一个数,但是他有一棵线段树维护了 AA 的区间和。线段树由 X1,X2,,XN1X_1, X_2, \dots , X_{N-1} 给出,其中 XiX_i 是线段树先序遍历的第 ii 个非叶结点的划分点。

例如,如果 N=5,X=[2,1,4,3]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 有 MM 个区间 [L1,R1),[L2,R2),,[LM,RM)[L_1, R_1), [L_2, R_2), \dots , [L_M, R_M),他想知道,在所有 22N12^{2N-1} 个线段树结点的子集中,有多少个子集 SS 满足以下条件:

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

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

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

输入格式

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

输入的第二行包含 N1N - 1 个整数 X1,X2,,XN1X_1, X_2, \dots , X_{N-1}

接下来 MM 行,每行包含两个整数 Li,RiL_i, R_i,表示一个区间。

输出格式

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

2 1
1
0 2
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

提示

样例 1 解释

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

数据范围

对于所有测试数据:

  • 2N2×1052 \le N \le 2 \times 10^5
  • $1 \le M \le \min \{\frac{N(N+1)}{2}, 2 \times 10^5\}$,
  • 1iN1,1XiN1\forall 1 \le i \le N - 1, 1 \le X_i \le N - 1
  • 保证 XiX_i 正确描述了一棵线段树,
  • 1iM,0Li<RiN\forall 1 \le i \le M, 0 \le L_i < R_i \le N
  • ij,(Li,Ri)(Lj,Rj)\forall i \ne j,(L_i, R_i) \ne (L_j, R_j )