题意

题目链接。

数轴上有若干传送门，初始是关闭或开启。对于关闭的传送门，经过后就会开启；对于开启的传送门，到达后会被传送到一个位置，然后会关闭。求从 $0$ 点走到 $x_n+1$，即最后一个传送门右边一格的所需时间。

解析

首先离散化。然后记 $f_i$ 为被在 $i$ 点的传送门传走再走回到 $i$ 点的时间。若该位置没有传送门，则记 $f_i=0$。容易发现已经过的传送门肯定是开启的，因此有 $f_i=x_i-y_i+\sum f_j,x_j\in [y_i,x_i-1]$，即路程长度加上被之间所有的传送门传一遍所需时间，发现这显然可以用前缀和维护。

求出所有 $f_i$ 之后，答案即为所有初始打开的传送门的 $f_i$ 之和加上路径长度。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+5;
const int mod=998244353;
struct node{
    int x,y,s;
}a[N];
int b[N],sum[N],f[N],ans,n;
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld%lld",&b[i*2-1],&b[i*2],&a[i].s);
        a[i].x=b[i*2-1];a[i].y=b[i*2];
    }
    sort(b+1,b+1+2*n);
    for(int i=1;i<=n;i++){
        a[i].x=lower_bound(b+1,b+1+2*n,a[i].x)-b;
        a[i].y=lower_bound(b+1,b+1+2*n,a[i].y)-b;
    }//离散化
    int now=1;
    for(int i=1;i<=2*n;i++){
        while(i==a[now].x&&now<=n){
            f[i]=(b[a[now].x]-b[a[now].y]+mod)%mod;
            f[i]=(f[i]+sum[a[now].x-1]-sum[a[now].y-1]+mod)%mod;
            if(a[now].s==1) ans=(ans+f[i])%mod;
            now++;
        }//求 fi 并统计答案
        sum[i]=(sum[i-1]+f[i])%mod;//前缀和维护
    }
    ans=(ans+b[a[n].x]+1)%mod;//加上路径总长度
    printf("%lld\n",ans);
    return 0;
}