60 分求调
查看原帖
60 分求调
554145
Night_sea_64楼主2024/5/19 13:47

哪位好心的大佬来帮帮我,蒟蒻感激不尽。

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int mod=998244353;
int n,m,q,s[200010],s2[200010];
struct node{int r,x,x2;}a[200010];
bool operator<(const node &x,const node &y){
    return x.r<y.r;
}
signed main()
{
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++)
    {
        int l;
        cin>>l>>a[i].r>>a[i].x;
        a[i].x%=mod;
        a[i].x2=a[i].x*a[i].x%mod;
    }
    sort(a+1,a+m+1);
    for(int i=1;i<=m;i++)
    {
        s[i]=(s[i-1]+(a[i].r-a[i-1].r)*a[i].x%mod)%mod;
        s2[i]=(s2[i-1]+(a[i].r-a[i-1].r)*a[i].x2%mod)%mod;
    }
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        int pl=lower_bound(a+1,a+m+1,(node){l,0,0})-a-1;
        int pr=lower_bound(a+1,a+m+1,(node){r,0,0})-a;
        int lcnt=(l-a[pl].r-1)%mod;
        int rcnt=(a[pr].r-r)%mod;
        int sum=(s[pr]+mod-s[pl])%mod;
        int sum2=(s2[pr]+mod-s2[pl])%mod;
        sum=(sum+lcnt*(mod-a[pl+1].x)%mod)%mod;
        sum=(sum+rcnt*(mod-a[pr].x)%mod)%mod;
        sum2=(sum2+lcnt*(mod-a[pl+1].x2)%mod)%mod;
        sum2=(sum2+rcnt*(mod-a[pr].x2)%mod)%mod;
        cout<<((r-l+1)%mod*sum2%mod+mod-sum*sum%mod)%mod<<endl;
    }
    return 0;
}

验证码 when 祭

2024/5/19 13:47
加载中...