P3932 浮游大陆的68号岛

题面:https://www.luogu.org/problem/P3932

本题中在设在x左边的区间为[l1,r1],在x右边的区间为[l2,r2]
则ansl=∑(d(x)-d(i))*a(i),(i=l1,...,r1)
ansl=∑d(x)*a(i)-∑d(i)*a(i)
ansl=d(x)*∑a(i)-∑d(i)*a(i)
ansr同理,这样就可用前缀和维护了.Code:
#include
#include
#include
#include
#include
using namespace std;
const int N=200005;
int n,m;
long long d[N],a[N],suma[N],sumd[N],sum[N],mod=19260817;
long long left(int x,int l,int r){if(l>r){return 0;}long long ans1=((suma[r]-suma[l-1])%mod+mod)%mod;ans1=ans1*sumd[x]%mod;long long ans2=((sum[r]-sum[l-1])%mod+mod)%mod;return ((ans1-ans2)%mod+mod)%mod;
}
long long right(int x,int l,int r){if(l>r){return 0;}long long ans1=((suma[r]-suma[l-1])%mod+mod)%mod;ans1=ans1*sumd[x]%mod;long long ans2=((sum[r]-sum[l-1])%mod+mod)%mod;return ((ans2-ans1)%mod+mod)%mod;
}
int main(){int x,l,r;scanf("%d%d", &n,&m);for(int i=2;i<=n;i++) {scanf("%lld",&d[i]);d[i]%=mod;sumd[i]=(sumd[i-1]+d[i])%mod;}for(int i=1;i<=n;i++) {scanf("%lld",&a[i]);suma[i]=(suma[i-1]+(a[i]%=mod))%mod;sum[i]=(sum[i-1]+ a[i]*sumd[i]%mod)%mod;}for(int i=1;i<=m;i++) {scanf("%d%d%d",&x,&l,&r);printf("%lld\n",(left(x,l,min(r, x-1))+right(x,max(l, x+1),r))%mod);}return 0;
}

转载于:https://www.cnblogs.com/ukcxrtjr/p/11505653.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！