Telepanting
Contest: Codeforces Global Round 15
Difficulty rating: 2200
Tags: binary search, data structures, dp, sortings

An ant moves on the real line with constant speed of $$$1$$$ unit per second. It starts at $$$0$$$ and always moves to the right (so its position increases by $$$1$$$ each second).

There are $$$n$$$ portals, the $$$i$$$-th of which is located at position $$$x_i$$$ and teleports to position $$$y_i < x_i$$$. Each portal can be either active or inactive. The initial state of the $$$i$$$-th portal is determined by $$$s_i$$$: if $$$s_i=0$$$ then the $$$i$$$-th portal is initially inactive, if $$$s_i=1$$$ then the $$$i$$$-th portal is initially active. When the ant travels through a portal (i.e., when its position coincides with the position of a portal):

- if the portal is inactive, it becomes active (in this case the path of the ant is not affected);
- if the portal is active, it becomes inactive and the ant is instantly teleported to the position $$$y_i$$$, where it keeps on moving as normal.

How long (from the instant it starts moving) does it take for the ant to reach the position $$$x_n + 1$$$? It can be shown that this happens in a finite amount of time. Since the answer may be very large, compute it modulo $$$998\,244\,353$$$.

Input format:
The first line contains the integer $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — the number of portals.

The $$$i$$$-th of the next $$$n$$$ lines contains three integers $$$x_i$$$, $$$y_i$$$ and $$$s_i$$$ ($$$1\le y_i < x_i\le 10^9$$$, $$$s_i\in\{0,1\}$$$) — the position of the $$$i$$$-th portal, the position where the ant is teleported when it travels through the $$$i$$$-th portal (if it is active), and the initial state of the $$$i$$$-th portal.

The positions of the portals are strictly increasing, that is $$$x_1<x_2<\cdots<x_n$$$. It is guaranteed that the $$$2n$$$ integers $$$x_1, \, x_2, \, \dots, \, x_n, \, y_1, \, y_2, \, \dots, \, y_n$$$ are all distinct.

Output format:
Output the amount of time elapsed, in seconds, from the instant the ant starts moving to the instant it reaches the position $$$x_n+1$$$. Since the answer may be very large, output it modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Explanation of the first sample: The ant moves as follows (a curvy arrow denotes a teleporting, a straight arrow denotes normal movement with speed $$$1$$$ and the time spent during the movement is written above the arrow). $$$$$$ 0 \stackrel{6}{\longrightarrow} 6 \leadsto 5 \stackrel{3}{\longrightarrow} 8 \leadsto 1 \stackrel{2}{\longrightarrow} 3 \leadsto 2 \stackrel{4}{\longrightarrow} 6 \leadsto 5 \stackrel{2}{\longrightarrow} 7 \leadsto 4 \stackrel{2}{\longrightarrow} 6 \leadsto 5 \stackrel{4}{\longrightarrow} 9 $$$$$$ Notice that the total time is $$$6+3+2+4+2+2+4=23$$$.

Explanation of the second sample: The ant moves as follows (a curvy arrow denotes a teleporting, a straight arrow denotes normal movement with speed $$$1$$$ and the time spent during the movement is written above the arrow). $$$$$$ 0 \stackrel{454971987}{\longrightarrow} 454971987 \leadsto 406874902 \stackrel{48097086}{\longrightarrow} 454971988 $$$$$$ Notice that the total time is $$$454971987+48097086=503069073$$$.

Explanation of the third sample: Since all portals are initially off, the ant will not be teleported and will go straight from $$$0$$$ to $$$x_n+1=899754846+1=899754847$$$.

Example input:
4
3 2 0
6 5 1
7 4 0
8 1 1

Example output:
23

Example input:
1
454971987 406874902 1

Example output:
503069073

Editorial:
Solution 1
The key insight is realizing that, if at some point the ant is located at position $$$x$$$, then all the portals with $$$x_i < x$$$ are active. One can prove this by induction on the time $$$t$$$. Indeed, when $$$t = 0$$$, $$$x = 0$$$ and there are no portals with $$$x_i < x$$$. Now suppose this is true at time $$$t$$$, and let $$$x$$$ be the position of the ant at that time. There are three possible scenarios to consider.
• If there is no portal at position $$$x$$$, then the statement is trivially true at time $$$t + 1$$$.
• If there is an inactive portal at position $$$x$$$, then that portal will become active and the position of the ant at time $$$t + 1$$$ will be $$$x + 1$$$, so all the portals with $$$x_i < x + 1$$$ will be active.
• If there is an active portal at position $$$x$$$, the ant will be teleported to some position $$$y < x$$$, and thus at time $$$t + 1$$$ it will be at position $$$y + 1 \le x$$$. Since all the portals with $$$x_i < x$$$ were active in the first place, and $$$y + 1 \le x$$$, all the portals with $$$x_i < y + 1$$$ will be active as well.
Let $$$q_i$$$ be the time the ant needs to go from the position $$$x_i$$$ to the position $$$x_i$$$ again assuming that all the portals $$$1, \, 2, \, \dots, \, i$$$ are active.
In order to find a formula for $$$q_i$$$, let us describe the movement of the ant when it starts from position $$$x_i$$$ and the portals $$$1, 2, \dots, i$$$ are active.
• The ant gets instantly teleported to $$$y_i$$$.
• The ant walks from $$$y_i$$$ to $$$x_{j_i}$$$, where $$$j_i \le i$$$ is the smallest index so that $$$y_i < x_{j_i}$$$.
• The ant walks for $$$q_{j_i}$$$ seconds and it ends up in $$$x_{j_i}$$$ with the portal inactive.
• The ant walks from $$$x_{j_i}$$$ to $$$x_{j_i+1}$$$.
• The ant walks for $$$q_{j_i+1}$$$ seconds and it ends up in $$$x_{j_i+1}$$$ with the portal inactive.
• $$$\cdots$$$
• The ant walks for $$$q_{i-1}$$$ seconds and it ends up in $$$x_{i-1}$$$ with the portal inactive.
• The ant walks from $$$x_{i-1}$$$ to $$$x_i$$$.
Adding up the contributions of the steps described above, we obtain the following recurrence for $$$q_i$$$: $$$$$$ q_i = (x_i - y_i) + q_{j_i} + q_{j_i + 1} + \cdots + q_{i - 1}. $$$$$$
Let $$$A$$$ be the set of portals that are initially active. The answer to the problem is given by the formula (which can be proven analyzing the movement of the ant as we have done to prove the recurrence relation for $$$q_i$$$) $$$$$$ x_n + 1 + \sum_{i \in A} q_i. $$$$$$
Using a binary search to identify $$$j_i$$$ and keeping the prefix sums of $$$q_1, \, q_2, \, \dots, \, q_n$$$, one can implement the described solution in $$$O(n\log n)$$$.
Complexity: $$$O(n\log n)$$$.
$$$$$$$$$$$$
Solution 2
Let $$$z_i$$$ be the index of the teleporter reached immediately after using teleporter $$$i$$$ (it can be computed by binary search).
Let $$$\text{dp}_{i, 0}$$$ be the number of times $$$x_i$$$ is reached. Let $$$\text{dp}_{i, 1}$$$ be the number of times the teleporter $$$i$$$ is used. Then, the answer is easy to calculate: each time the teleporter $$$i$$$ is active you spend $$$x_{z_i} - y_i$$$ time, and each time the teleporter $$$i$$$ is inactive you spend $$$x_{i + 1} - x_i$$$ time. Summing up all the contributions, the answer turns out to be $$$$$$ \sum_{i = i}^n \: [\text{dp}_{i, 1}(x_{z_i} - y_i) + (\text{dp}_{i, 0} - \text{dp}_{i, 1})(x_{i + 1} - x_i)], $$$$$$ where $$$x_{n + 1} = x_n + 1$$$.
Now we find recurrences for $$$\text{dp}_{i, 0}$$$ and $$$\text{dp}_{i, 1}$$$. The crucial observation is that $$$\text{dp}_{i, 0}$$$ has the same parity of $$$s_i \oplus 1$$$, where $$$\oplus$$$ denotes bitwise XOR. Thus, it is not hard to see that, for $$$1 \le i \le n$$$, $$$$$$ \begin{align*} \text{dp}_{i + 1, 0} = \sum_{z_j = i + 1} \text{dp}_{j, 1} + \frac{\text{dp}_{i, 0} + (s_i \oplus 1)}{2} \implies \text{dp}_{i, 0} & = 2\left(\text{dp}_{i + 1, 0} - \sum_{z_j = i + 1} \text{dp}_{j, 1}\right) - (s_i \oplus 1), \\ \text{dp}_{i, 1} & = \frac{\text{dp}_{i, 0} - (s_i \oplus 1)}{2}. \end{align*} $$$$$$
It now suffices to iterate over the indices $$$i$$$ in decreasing order.
Complexity: $$$O(n\log n)$$$.