{"problem":{"name":"[WC2024] 线段树","description":{"content":"小 Y 最近学会了如何用线段树维护序列，并支持区间求和的操作。 **以下给出本题中线段树的定义。 该定义可能和你熟知的线段树有区别。** - 线段树是一种有根的二叉树，其每个节点对应了序列上的一个区间 $[l, r)$，其中根节点对应 $[0, n)$。 - 对于每个节点，若其代表的序列区间 $[l, r)$ 满足 $r - l = 1$，则其为叶节点；否则存在整数 $m(l < m < r)","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10145"},"statements":[{"statement_type":"Markdown","content":"小 Y 最近学会了如何用线段树维护序列，并支持区间求和的操作。\n\n**以下给出本题中线段树的定义。 该定义可能和你熟知的线段树有区别。**\n\n- 线段树是一种有根的二叉树，其每个节点对应了序列上的一个区间 $[l, r)$，其中根节点对应 $[0, n)$。\n- 对于每个节点，若其代表的序列区间 $[l, r)$ 满足 $r - l = 1$，则其为叶节点；否则存在整数 $m(l < m < r)$，满足其左儿子代表区间 $[l, m)$，右儿子代表区间 $[m, r)$。\n- 线段树的形态取决于每个非叶结点的划分点 $m$ 的选择。\n- 在区间求和的问题上，对于序列 $a_0, a_1, \\dots , a_{n-1}$，线段树的每个结点 $[l, r)$ 维护了\n$(a_l + a_{l+1} + \\cdots + a_{r-1})$ 的值。\n\n小 J 有一个长度为 $N$ 的数组 $A_0, A_1, \\dots , A_{N-1}$，他并不知道 $A$ 中的任何一个数，但是他有一棵线段树维护了 $A$ 的区间和。线段树由 $X_1, X_2, \\dots , X_{N-1}$ 给出，其中 $X_i$ 是线段树先序遍历的第 $i$ 个非叶结点的划分点。\n\n例如，如果 $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)$。\n\n小 J 有 $M$ 个区间 $[L_1, R_1), [L_2, R_2), \\dots , [L_M, R_M)$，他想知道，在所有 $2^{2N-1}$ 个线段树结点的子集中，有多少个子集 $S$ 满足以下条件：\n\n- 如果已知 $S$ 中所有结点维护的值，则每个 $[L_i\n, R_i)$ 区间的和都能被唯一确定。\n\n例如，如果已知 $[0, 1), [1, 2)$，就能确定 $[0, 2)$ 的和；反过来，如果已知 $[0, 1), [0, 2)$，也能确定 $[1, 2)$ 的和。但如果仅已知 $[0, 2), [2, 4)$ 则不能确定 $[0, 3)$ 或 $[1, 2)$ 的和。\n\n由于答案很大，你需要输出答案对 $998244353$ 取模后的值。\n\n## Input\n\n输入的第一行包含两个整数 $N, M$，分别表示数组长度和区间个数。\n\n输入的第二行包含 $N - 1$ 个整数 $X_1, X_2, \\dots , X_{N-1}$。\n\n接下来 $M$ 行，每行包含两个整数 $L_i, R_i$，表示一个区间。\n\n## Output\n\n输出一行一个整数表示答案对 $998244353$ 取模后的值。\n\n[samples]\n\n## Note\n\n**样例 1 解释**\n\n只有当直接知道 $[0, 2)$ 的总和或同时知道 $[0, 1)$ 和 $[1, 2)$ 的总和时才能知道 $[0, 2)$ 的总和，因此总的方案数为 $2^2 + 1 = 5$。\n\n### 数据范围\n\n对于所有测试数据：\n- $2 \\le N \\le 2 \\times 10^5$，\n- $1 \\le M \\le \\min \\{\\frac{N(N+1)}{2}, 2 \\times 10^5\\}$，\n- $\\forall 1 \\le i \\le N - 1, 1 \\le X_i \\le N - 1$，\n- 保证 $X_i$ 正确描述了一棵线段树，\n- $\\forall 1 \\le i \\le M, 0 \\le L_i < R_i \\le N$，\n- $\\forall i \\ne j,(L_i, R_i) \\ne (L_j, R_j )$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/ncb7tdfe.png)","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10145","tags":["2024","WC"],"sample_group":[["2 1\n1\n0 2","5"],["2 1\n1 \n1 2","5"],["5 2\n2 1 4 3\n1 3\n2 5","193"],["10 10\n5 2 1 3 4 7 6 8 9\n0 1\n0 2\n0 3\n0 4\n0 5\n0 6\n0 7\n0 8\n0 9\n0 10","70848"]],"created_at":"2026-03-03 11:09:25"}}