{"problem":{"name":"「REOI-1」深潜的第六兽","description":{"content":"现在有一只〈第六兽〉，在某一次的「分裂增生」时分裂出了 $n$ 个碎块，这些碎块会笔直向上飞去，如果其中一块碎块遇到了一座浮空岛（为了研究方便，我们不妨将它当成一条二维空间中的线段处理），便会迅速占据它，并一分为二，再次从浮空岛的两端笔直向上飞去。 不过好在，那些只是一些无关紧要最为荒凉毫无人烟的岛屿，但如果就这样放任它们继续肆虐，势必会给那些至关重要的浮空岛带来毁灭性的打击。于是乎，负责清理〈","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8463"},"statements":[{"statement_type":"Markdown","content":"现在有一只〈第六兽〉，在某一次的「分裂增生」时分裂出了 $n$ 个碎块，这些碎块会笔直向上飞去，如果其中一块碎块遇到了一座浮空岛（为了研究方便，我们不妨将它当成一条二维空间中的线段处理），便会迅速占据它，并一分为二，再次从浮空岛的两端笔直向上飞去。\n\n不过好在，那些只是一些无关紧要最为荒凉毫无人烟的岛屿，但如果就这样放任它们继续肆虐，势必会给那些至关重要的浮空岛带来毁灭性的打击。于是乎，负责清理〈第六兽〉的军官们，决定以他们所在的岛屿为直线建立 $x$ 轴，并以重力的方向为正方向建立 $y$ 轴，他们总共监测到了 $m$ 座浮空岛，并确定了那些碎块分裂出的位置（距离 $x$ 轴的位置视作无限远），于是他们想知道，如果放任这些碎块，那么当它们到达军官的位置时，最终会有多少碎块。\n\n注意，若一座浮空岛的 $ l_i $ 与 $ r_i $ 相同，即为一个点， 〈第六兽〉占据后仍然会分裂成两只，从这个点向上飞去。\n\n**提示：浮空岛作为实体显然不会重叠。**\n\n**简要题意：**\n\n在一个平面直角坐标系上有 $m$ 条平行于 x 轴的线段，第 $i$ 条线段为 $(l_i,h_i)$ 与 $(r_i,h_i)$ 的连线。特别注意 $l_i$ 可与 $r_i$ 相等，此时线段变为一个点。\n\n在直线 $y=10^9$ 上有 $n$ 个点，分别位于 $(x_i,10^9)$。\n\n现在，这些点逐渐向下（y轴负方向）移动。若触碰到线段，则会一分为二，分裂出的两个点分别从线段的两端继续向下移动。\n\n特别地，若线段为一个点，则会原地分裂成 2 个。\n\n问所有初始点在经历了线段的分裂后，在最后会有多少个点掉在 $ x $ 轴上\n\n## Input\n\n第一行输入两个数 $ n $ 和 $ m $。\n\n接下来 $ m $ 行，每行三个数 $ l_i $ , $ r_i $ , $ h_i $ ,分别描述一座被视作线段的浮空岛的左端点横坐标，右端点横坐标，以及线段的纵坐标（ $ 0 \\leq l_i,r_i,h_i \\leq 10^5，l_i \\leq r_i$）。\n\n接下来一行 $ n $ 个数，$ x_i $表示第 $ i $ 个碎块的横坐标（ $ 0 \\leq x_i \\leq 10^5 $）。\n\n## Output\n\n输出一个整数 $ ans $ ，表示最后会有多少个碎块落在 $ x $ 轴上，答案对 $998244353$ 取模。\n\n[samples]\n\n## Background\n\n“〈十七兽〉全都不会飞。因此，在它们毁灭大地以后，悬浮大陆群还能像这样浮在天空。\n\n“可是，只有〈深潜的第六兽〉在本身留在大地的同时，还能对悬浮大陆群发动攻击。它有两种能力，『分裂增生』和『快速茁壮』。\n\n“留在地表的本体会让身体分裂出几万个碎块，然后随风飞扬，等待碰巧飘流到某座悬浮岛。抵达岛上以后，它会当场发育茁壮，大约六到八小时过后就能占据并毁灭整座岛。”\n\n## Note\n\n样例解释：\n\n注意， $y$ 轴正方向为重力方向。\n在坐标轴中，横坐标为 $x$ 的碎块，先掉到纵坐标为2的线段上，然后分成两个从 $1$ 和 $3$ 往下掉，$3$ 的那个掉到了纵坐标为1的线段上，分成两个从 $2$ 和 $6$ 往下掉，第一个碎块一共变成了 $3$ 块，分别掉在 $1，2，6$ ，第二个碎块一共变成了两个碎块，分别掉在 $2，6$。\n\n| 子问题 | 特殊限制条件 | 分值 |\n| :-----------: | :-----------: | :-----------: |\n| 1 | $ 1\\leq n,m \\leq 10 $ | 10 |\n| 2 | $ 1\\leq n,m \\leq 100 $ | 5 |\n| 3 | $ 1\\leq n\\leq 10^4， 1\\leq m \\leq 5\\times 10^5 $ | 35 |\n| 4 |$ 1\\leq n,m \\leq 5\\times 10^5 $|50|\n\n本题各个子问题之间不捆绑测试。\n\n对于 $100\\%$ 的数据 $ 1\\leq n,m \\leq 5\\times 10^5 $，所有数字均为非负整数。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8463","tags":["洛谷原创","洛谷月赛"],"sample_group":[["2 2\n1 3 2\n2 6 1\n3 5","5"]],"created_at":"2026-03-03 11:09:25"}}