ABC158 F. Removing Robots

問題

数直線上に1～Nの番号のついたロボットが置かれている。
ロボットiは座標X_iにあり、スイッチを入れるとD_iだけ移動し、直後取り除かれる。
また、以下の操作を好きなだけ行える。

• ロボットを1つスイッチを入れる。どれかのロボットが移動している間はこの操作は行えない。

ロボットは、X_i以上X_i+D_i未満に他のロボットがあった場合、そのロボットもスイッチが入り、これが再帰的に繰り返される。

これらの操作を繰り返したあとに残っているロボットの組合せは何通りありえるか？
998244353で割ったあまりを求めよ。

制約

• 1 <= N <= 2*10^5
• -10^9 <= X_i <= 10^9
• 1 <= D_i <= 10^9
• X_i != X_j (i != j)

解法

あるロボットiが起動した場合、連鎖的にどのロボットまで起動してしまうか？がわかれば、X_iの大きいロボットから逆方向に向かってdpで求められる。
以下、ロボットをX_i順に並べたもので考える。
このdpは、
dp[i] += dp[i+1]
dp[i] += dp[連鎖最後のロボットのindex + 1]
で求められる。

ロボットiを起動した場合の連鎖で起動する最後のロボットのindexをR[i]とする。
X_iが大きい方から処理していくことを考えると、R[i] = max(i, X_i以上X_i+D_i未満にあるR[j])で求められるので、SegmentTreeでRangeMaximumQueryを行えば求めていける。(X_iとX_i+D_iは座圧しておく)