P10211 [CTS2024] 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 be different from the segment tree you are familiar with.** - A segment tree is a rooted binary tree. Each node corresponds to an interval $[l, r)$ on the sequence, where 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 represents $[l, m)$ and its right child represents $[m, r)$. - The shape of the segment tree depends on the choice of the split point $m$ for each non-leaf node. - For the range sum problem, for the sequence $a_0, a_1, \dots, a_{n-1}$, each node $[l, r)$ in the segment tree maintains the value of $(a_l + a_{l+1} + \cdots + a_{r-1})$. Little J has an array of length $N$, $A_0, A_1, \dots, A_{N-1}$. 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 nodes in the segment tree, in preorder traversal, are $[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 $S$ of the $2N - 1$ segment tree nodes, how many subsets $S$ satisfy the following condition: - If the values maintained by all nodes in $S$ are known, then the sum over each interval $[L_i, R_i)$ can be uniquely determined. For example, if $[0, 1)$ and $[1, 2)$ are known, then the sum over $[0, 2)$ can be determined. Conversely, if $[0, 1)$ and $[0, 2)$ are known, then the sum over $[1, 2)$ can also be determined. But if only $[0, 2)$ and $[2, 4)$ are known, then the sum over $[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 line with one integer, 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 total sums of $[0, 1)$ and $[1, 2)$, can you determine the total sum of $[0, 2)$. Therefore, the total number of valid choices 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)$. Subtask 1 (6 points): $N \le 10$. Subtask 2 (18 points): $N \le 100$. Subtask 3 (9 points): $N \le 500$. Subtask 4 (17 points): $N \le 5000$. Subtask 5 (10 points): $M = 1$. Subtask 6 (13 points): $M \le 5$. Subtask 7 (7 points): $M = N, L_i = 0, R_i = i$. Subtask 8 (20 points): No additional constraints. Translated by ChatGPT 5