P10145 [WC2024] Segment Tree

Little Y has recently learned how to use a segment tree to maintain a sequence and support range sum queries. **Below is the definition of the segment tree used in this problem. This definition may differ from the one you are familiar with.** - A segment tree is a rooted binary tree. Each node corresponds to an interval $[l, r)$ on the sequence, and the root corresponds to $[0, n)$. - For each node, if its interval $[l, r)$ satisfies $r - l = 1$, then it is a leaf node. Otherwise, there exists an integer $m(l < m < r)$ such that its left child corresponds to $[l, m)$ and its right child corresponds to $[m, r)$. - The shape of the segment tree depends on the choice of the split point $m$ for each non-leaf node. - For range sum problems, for the sequence $a_0, a_1, \dots, a_{n-1}$, each node $[l, r)$ in the segment tree maintains the value $(a_l + a_{l+1} + \cdots + a_{r-1})$. Little J has an array $A_0, A_1, \dots, A_{N-1}$ of length $N$. He does not know any value in $A$, but he has a segment tree that maintains the range sums of $A$. The segment tree is given by $X_1, X_2, \dots, X_{N-1}$, where $X_i$ is the split point of the $i$-th non-leaf node in the preorder traversal of the segment tree. For example, if $N = 5, X = [2, 1, 4, 3]$, then the preorder traversal of the nodes in the segment tree is $[0, 5), [0, 2), [0, 1), [1, 2), [2, 5), [2, 4), [2, 3), [3, 4), [4, 5)$. Little J has $M$ intervals $[L_1, R_1), [L_2, R_2), \dots, [L_M, R_M)$. He wants to know: among all subsets of the $2N - 1$ segment tree nodes, how many subsets $S$ satisfy the following condition: - If the maintained values of all nodes in $S$ are known, then the sum of each interval $[L_i, R_i)$ can be uniquely determined. For example, if $[0, 1)$ and $[1, 2)$ are known, then the sum of $[0, 2)$ can be determined. Conversely, if $[0, 1)$ and $[0, 2)$ are known, then the sum of $[1, 2)$ can also be determined. But if only $[0, 2)$ and $[2, 4)$ are known, then the sum of $[0, 3)$ or $[1, 2)$ cannot be determined. Since the answer can be very large, you need to output the answer modulo $998244353$.

The first line contains two integers $N, M$, representing the array length and the number of intervals. The second line contains $N - 1$ integers $X_1, X_2, \dots, X_{N-1}$. The next $M$ lines each contain two integers $L_i, R_i$, representing an interval.

Output one integer in one line, representing the answer modulo $998244353$.

**Explanation for Sample 1** Only when you directly know the total sum of $[0, 2)$, or when you know both the sums of $[0, 1)$ and $[1, 2)$ at the same time, can you determine the sum of $[0, 2)$. Therefore, the total number of valid ways is $2^2 + 1 = 5$. ### Constraints For all testdata: - $2 \le N \le 2 \times 10^5$. - $1 \le M \le \min \{\frac{N(N+1)}{2}, 2 \times 10^5\}$. - $\forall 1 \le i \le N - 1, 1 \le X_i \le N - 1$. - It is guaranteed that $X_i$ correctly describes a segment tree. - $\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)$.  Translated by ChatGPT 5