60pts 求助
  • 板块P10511 方差
  • 楼主I_will_AKIOI我心依旧
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/5/20 21:27
  • 上次更新2024/5/21 10:59:43
查看原帖
60pts 求助
565265
I_will_AKIOI我心依旧楼主2024/5/20 21:27

rt,或许是取模不完全 or 其他小细节。

#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
int n,m,q;
int x[200005],y[200005],z[200005],sum1[200005],sum2[200005];
signed main()
{
  ios::sync_with_stdio(0);
  //freopen("sample1.in","r",stdin);
  //freopen("ans.out","w",stdout);
  cin>>n>>m>>q;
  for(int i=1;i<=m;i++)
  {
    cin>>x[i]>>y[i]>>z[i];
    z[i]%=mod;
    sum1[i]=(sum1[i-1]+z[i]%mod*(y[i]-x[i]+1)%mod)%mod;
    sum2[i]=(sum2[i-1]+z[i]%mod*z[i]%mod*(y[i]-x[i]+1)%mod)%mod;
  }
  while(q--)
  {
    int l,r,cnt1=0,cnt2=0,num1,num2,ans;
    cin>>l>>r;
    num1=lower_bound(x+1,x+m+1,l)-x;
    num2=upper_bound(y+1,y+m+1,r)-y-1;
    if(num1>num2+1)
    {
      cout<<0<<"\n";
      continue;
    }
    cnt1=(((sum1[num2]-sum1[num1-1])%mod+mod)%mod+((x[num1]-l)%mod+mod)%mod*z[num1-1]%mod+((r-y[num2])%mod+mod)%mod*z[num2+1]%mod)%mod;
    cnt2=(((sum2[num2]-sum2[num1-1])%mod+mod)%mod+((x[num1]-l)%mod+mod)%mod*z[num1-1]%mod*z[num1-1]%mod+((r-y[num2])%mod+mod)%mod*z[num2+1]%mod*z[num2+1]%mod)%mod;
    ans=((((r-l+1)%mod+mod)%mod*cnt2%mod-cnt1%mod*cnt1%mod)%mod+mod)%mod;
    cout<<ans<<"\n";
  }
  return 0;
}
2024/5/20 21:27
加载中...