P8463 "REOI-1" The Sixth Beast of Deep Diving

"None of the 'Seventeen Beasts' can fly. Therefore, after they destroyed the earth, the floating continents could still remain suspended in the sky. "However, only the 'Sixth Beast of Deep Diving' can, while its main body stays on the ground, still attack the floating continents. It has two abilities: 'Split Proliferation' and 'Rapid Growth'. "The main body staying on the surface will split into tens of thousands of fragments, which then drift with the wind, waiting to accidentally float onto some floating island. After reaching an island, it will grow rapidly on the spot, and after about six to eight hours, it can occupy and destroy the entire island."

Now there is a 'Sixth Beast'. During one "Split Proliferation", it split into $n$ fragments. These fragments will fly straight upward. If one fragment encounters a floating island (for convenience of research, we treat it as a line segment in 2D space), it will quickly occupy it, split into two, and then fly straight upward again from the two ends of the floating island. Fortunately, these are only some unimportant, most barren and uninhabited islands. But if we let them continue to wreak havoc, they will surely deal a devastating blow to those crucial floating islands. Therefore, the officers responsible for eliminating the 'Sixth Beast' decided to use the island they are on as a straight line to define the $x$ axis, and to use the direction of gravity as the positive direction of the $y$ axis. They monitored a total of $m$ floating islands, and determined the positions where those fragments split (the distance from the $x$ axis is regarded as infinite). They want to know: if we do nothing and let these fragments go, when they reach the officers' position, how many fragments will there finally be. Note that if a floating island has $l_i$ equal to $r_i$, then it is a point. After the 'Sixth Beast' occupies it, it will still split into two and fly upward from this point. **Hint: As physical objects, floating islands obviously do not overlap.** **Brief statement:** In a Cartesian coordinate system, there are $m$ line segments parallel to the $x$ axis. The $i$-th segment is the segment connecting $(l_i,h_i)$ and $(r_i,h_i)$. Note that $l_i$ may equal $r_i$, in which case the segment becomes a point. On the line $y=10^9$, there are $n$ points located at $(x_i,10^9)$. Now these points move downward gradually (the negative direction of the $y$ axis). If a point touches a segment, it splits into two, and the two new points continue moving downward from the two ends of the segment, respectively. In particular, if the segment is a point, it splits into 2 at the same position. Ask: after all initial points undergo the splits caused by the segments, how many points will finally fall onto the $x$ axis.

The first line contains two integers $n$ and $m$. The next $m$ lines each contain three integers $l_i$, $r_i$, $h_i$, describing the $x$-coordinate of the left endpoint, the $x$-coordinate of the right endpoint, and the $y$-coordinate of the segment, respectively ($0 \leq l_i,r_i,h_i \leq 10^5，l_i \leq r_i$). The next line contains $n$ integers $x_i$, where $x_i$ is the $x$-coordinate of the $i$-th fragment ($0 \leq x_i \leq 10^5$).

Output one integer $ans$, the number of fragments that finally land on the $x$ axis. The answer should be taken modulo $998244353$.

Sample explanation: Note that the positive direction of the $y$ axis is the direction of gravity. In the coordinate system, the fragment with $x$-coordinate $x$ first falls onto the segment at $y=2$, then splits into two and falls downward from $1$ and $3$. The one at $3$ falls onto the segment at $y=1$, splits into two and falls downward from $2$ and $6$. The first fragment becomes $3$ fragments in total, landing at $1,2,6$. The second fragment becomes $2$ fragments in total, landing at $2,6$. | Subtask | Special Constraints | Score | | :-----------: | :-----------: | :-----------: | | 1 | $ 1\leq n,m \leq 10 $ | 10 | | 2 | $ 1\leq n,m \leq 100 $ | 5 | | 3 | $ 1\leq n\leq 10^4， 1\leq m \leq 5\times 10^5 $ | 35 | | 4 | $ 1\leq n,m \leq 5\times 10^5 $ | 50 | The subtasks of this problem are not bundled for testing. For $100\%$ of the data, $1\leq n,m \leq 5\times 10^5$, and all numbers are non-negative integers. Constraints: Translated by ChatGPT 5