{"problem":{"name":"待黑白分明","description":{"content":"[Shiro](https://www.bilibili.com/video/BV1jb411k7wa) 所在的城市可以看成数轴上 $n$ 个坐标连续的点，其中 $i$  号点的高度为 $p_i$，保证 $p$ 是一个 $\\{1,2,\\ldots,n\\}$ 的排列。 3202 年的科技非常发达，发展出了虫洞列车技术。共有 $n$ 种列车，第 $i$ 种列车会经过所有高度大于等于 $i$ 的位置，","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":65536},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9152"},"statements":[{"statement_type":"Markdown","content":"[Shiro](https://www.bilibili.com/video/BV1jb411k7wa) 所在的城市可以看成数轴上 $n$ 个坐标连续的点，其中 $i$  号点的高度为 $p_i$，保证 $p$ 是一个 $\\{1,2,\\ldots,n\\}$ 的排列。\n\n3202 年的科技非常发达，发展出了虫洞列车技术。共有 $n$ 种列车，第 $i$ 种列车会经过所有高度大于等于 $i$ 的位置，每种列车线路都是双向的，也就是说可以乘列车从左到右，也可以从右到左。\n\nShiro 想在城市里转转，她定义一个位置集合 $S$ 合法，当且仅当我们将 $S$ 中的位置**按照高度排序**后，相邻的城市可以通过乘坐**一种**列车在中途不停靠的情况下直达。\n\n她会给你 $q$ 次询问，每次给定 $l,r$，你需要告诉 Shiro 所有位置的**高度**均在 $[l,r]$ 内的合法集合 $T$ 的数量对 $998244353$ 取模的结果。\n\n## Input\n\n第一行，两个正整数 $n,q$。\n\n第二行，$n$ 个正整数，表示 $p_{1,2,\\ldots,n}$。\n\n接下来 $q$ 行，第 $i$ 行两个正整数 $l_i, r_i$，表示第 $i$ 次询问的高度区间。\n\n## Output\n\n输出 $q$ 行，每行一个非负整数，表示答案。\n\n[samples]\n\n## Note\n\n**【样例解释】**\n\n第一组询问解释：\n\n合法的高度集合有：$\\{3\\},\\{4\\},\\{5\\},\\{3,5\\},\\{4,5\\}$。\n\n---\n\n**【数据范围】**\n\n对于 $100 \\%$ 的数据，$1\\le n,q\\le 2\\times {10}^5$，保证 $p$ 是一个排列，且 $1\\le l_i \\le r_i \\le n$。\n\n|子任务|$n\\le$|$q\\le$|特殊性质|分值|\n|-|-|-|-|-|\n|1|$15$|$1000$||$10$|\n|2|$1000$|$1000$||$15$|\n|3|||A|$5$|\n|4|||B|$30$|\n|5|$5\\times{10}^4$|$5\\times{10}^4$||$20$|\n|6||||$20$|\n\n特殊性质 A：$p_i=i$。\n\n特殊性质 B：$p$ 在所有长度为 $n$ 的排列中随机选取。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9152","tags":["洛谷原创","O2优化","分块","洛谷月赛","笛卡尔树"],"sample_group":[["5 3\n2 4 5 1 3\n3 5\n1 5\n1 4\n","5\n12\n6\n"]],"created_at":"2026-03-03 11:09:25"}}