做的最舒服的一道蓝题，在语文课上睡觉想出来了。

首先我们发现，假如我们在位置 ii，就表示 xjx_j 小于 ii 的虫洞必须都是开着的（因为都从它们经过了）。

所以为了避免重复计算，我们可以记录 ansians_{i} 表示如果到达这个点的时候是开启的，（从 yiy_i 开始）下一次回到这个点要走多少步，那么借助我们前面说的所有点都是开启的，ansians_{i} 应该就是 (xi−yi)(x_i - y_i) 加上在 [yi,xi][y_i,x_i] 这段区间里所有点的 ansans 值之和，这里可以用前缀和维护。

最后计算答案也很简单，每次找到一个开启的点，然后计算它和上一个出发点之间的距离加上之间所有点的 ansans 值之和，然后更新出发点为当前点就好啦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
signed main()
{
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    vector<bool> vis(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        int ch;
        cin >> ch;
        vis[i] = (ch == 1);
    }
    vector<int> ans(n + 1, 0), pre(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        auto pos = upper_bound(a.begin(), a.end(), b[i]) - a.begin();
        ans[i] = (a[i] - b[i] + mod) % mod;
        if (pos < i) {
            ans[i] += (pre[i - 1] - pre[pos - 1] + mod) % mod;
        }
        pre[i] = (pre[i - 1] + ans[i]) % mod;
    }
    int ls = 0, anss = 0;
    for (int i = 1; i <= n; i++) {
        if (vis[i]) {
            anss = (anss + (a[i] - ls + mod) + ans[i]) % mod;
            ls = a[i];
        }
        if (i == n && !vis[i]) {
            anss = (anss + (a[i] - ls) + mod) % mod;
            break;
        }
    }
    cout << (anss + 1 + mod) % mod;
    return 0;
}