【Luogu3932】浮游大陆的68号岛

problem

solution

codes

//1,2：各在左右：把所有物品从区间移到最左边的花费减去把所有物品从目标位置移到最左边的花费就是把所有物品从区间移到目标位置的花费，右边同理。
//3：若目标仓库在区间内部，将区间拆为两部分分别算。
//ans:所以只需要维护bi*xi和bi即可，用前缀和,复杂度线性
#include
using namespace std;
typedef long long LL;
const int maxn = (int)3e7+10;
const int mod = 19260817;
LL x[maxn], b[maxn];
LL xx[maxn], bb[maxn];//前缀和
int main(){LL n, m;cin>>n>>m;for(int i = 2; i <= n; i++){cin>>x[i];  x[i] += x[i-1]; x[i]%=mod;}for(int i = 1; i <= n; i++){cin>>b[i];  bb[i]=b[i]+bb[i-1]; bb[i]%=mod;xx[i] = x[i]*b[i]+xx[i-1];  xx[i]%=mod;}for(int i = 1; i <= m; i++){LL g, l, r, t;  cin>>g>>l>>r;if(g <= l)t = (xx[r]-xx[l-1])-x[g]*(bb[r]-bb[l-1]);else if(g >= r)t = x[g]*(bb[r]-bb[l-1])-(xx[r]-xx[l-1]);else t = (xx[r]-xx[g])-x[g]*(bb[r]-bb[g])+x[g]*(bb[g-1]-bb[l-1])-(xx[g-1]-xx[l-1]);//左边加右边即可，自己到自己为0t %= mod;if(t < 0)t += mod;cout<"\n";}return 0;
}

转载于:https://www.cnblogs.com/gwj1314/p/9444715.html

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