大阳历能过,复杂度没问题,看不出来哪里错了/kk
#include<iostream>
#include<cmath>
using namespace std;
#define int long long
const int N=1e7+10,p=998244353;
int n,k;
int a[N],l,r,sum,squ,cnt,squ1,sum1;
signed main(){
// freopen("ex.in","r",stdin);
// freopen("[].out","w",stdout);
cin>>n>>k;
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
if(a[i]>=0){
sum=(sum+a[i])%p;
squ=(squ+a[i]*a[i])%p;
++cnt;
}
else{
squ1=(squ1+a[i]*a[i]%p)%p;
sum1=(sum1+a[i])%p;
}
if(cnt==1) l=i;
}
// cout<<squ<<' '<<sum<<endl;
int ans=0;
ans=(ans+2*sum1+n-cnt)%p;
// cout<<ans<<endl;
r=n;
for(int i=1;i<=k;++i){
squ=(squ+2*sum+r-l+1)%p;
sum=(sum+r-l+1)%p;
while(l>=2 && abs(a[l-1]+i)>abs(a[l-1])){
// cout<<333333<<endl;
// cout<<a[l-1]+i<<endl;
sum=(sum+a[l-1]+i)%p; squ=(squ+(a[l-1]+i)*(a[l-1]+i))%p;
squ1=(squ1+p-a[l-1]*a[l-1]%p)%p;
--l;
}
// cout<<squ<<' '<<sum<<' '<<squ1<<endl;
ans=(ans+squ)%p;
ans=(ans+squ1)%p;
// cout<<ans<<endl;
}
cout<<ans<<endl;
return 0;
}
有没有神仙帮忙看看