题目来源：洛谷
题目描述
妖精仓库的储物点可以看做在一个数轴上。每一个储物点会有一些东西，同时他们之间存在距离。
每次他们会选出一个小妖精，然后剩下的人找到区间[l,r][l,r]储物点的所有东西，清点完毕之后问她，把这个区间内所有储物点的东西运到另外一个仓库的代价是多少？
比如储物点ii有xx个东西，要运到储物点jj，代价为 x × dist(i,j)
dist就是仓库间的距离。
当然啦，由于小妖精们不会算很大的数字，因此您的答案需要对19260817取模。
输入输出格式
输入格式：
第一行两个数表示n,m
第二行n-1个数，第i个数表示第i个储物点与第i+1个储物点的距离
第三行n个数，表示每个储物点的东西个数
之后m行每行三个数x l r
表示查询要把区间[l,r]储物点的物品全部运到储物点x的花费
输出格式：
对于每个询问输出一个数表示答案
输入输出样例
说明
对于30%的数据，n,m≤1000
对于另外20%的数据，所有储物点间的距离都为1
对于另外20%的数据，所有储物点的物品数都为1
对于100%的数据 ,n,m≤200000;ai,bi<=2⋅10^9
解析：
这道题的取模太™扯淡了。
这道题给出的数据明显是想让我们用前缀和优化。
作为一个明显的区间维护问题，本蒟蒻想到了线段树（因为我只学了线段树和分块 （逃）。
我们不管别的，先来看看这题具体怎么求解。
我们先计算出距离的前缀和数组d[]备着，来看看费用怎么算：
- 当l>x时，sum=w[i]*(d[i]-d[x]),l<=i<=r;
- 当r<x时，sum=w[i]*(d[x]-d[i]),l<=i<=r;
- 当l<=x<=r时，sum的值可看做前1，2种情况的合并
当我们搞定魔幻的取模，这题就过了。
我的垃圾代码：
1 #include<cstdio> 2 #include<iostream> 3 #define N 200010 4 #define ll long long 5 #define mod 19260817 6 //能取模的地方就取模 7 using namespace std; 8 ll d[N],w[N]; 9 struct segmentree{ 10 ll l,r; 11 ll sum1,sum2; 12 }t[N<<2]; 13 void built(ll p,ll l,ll r) 14 { 15 t[p].l=l;t[p].r=r; 16 if(t[p].l==t[p].r){ 17 t[p].sum1=w[l]%mod;//根据分配率，我们可以先维护w[i]的值 ，再统一乘上d[x] 18 t[p].sum2=w[l]*d[l]%mod; 19 return; 20 } 21 ll mid=(l+r)>>1; 22 built(p<<1,l,mid); 23 built(p<<1|1,mid+1,r); 24 t[p].sum1=(t[p<<1].sum1+t[p<<1|1].sum1)%mod; 25 t[p].sum2=(t[p<<1].sum2+t[p<<1|1].sum2)%mod; 26 } 27 ll ask1(ll p,ll l,ll r) 28 { 29 if(l<=t[p].l&&t[p].r<=r) return t[p].sum1%mod; 30 ll mid=(t[p].l+t[p].r)>>1; 31 ll val=0; 32 if(l<=mid) val=(val+ask1(p<<1,l,r))%mod; 33 if(r>mid) val=(val+ask1(p<<1|1,l,r))%mod; 34 return val; 35 } 36 ll ask2(ll p,ll l,ll r) 37 { 38 if(l<=t[p].l&&t[p].r<=r) return t[p].sum2%mod; 39 ll mid=(t[p].l+t[p].r)>>1; 40 ll val=0; 41 if(l<=mid) val=(val+ask2(p<<1,l,r))%mod; 42 if(r>mid) val=(val+ask2(p<<1|1,l,r))%mod; 43 return val; 44 } 45 int main() 46 { 47 ll m,n,x,l,r; 48 scanf("%lld%lld",&n,&m); 49 for(int i=1;i<n;i++) scanf("%lld",&d[i]); 50 for(int i=1;i<=n;i++) scanf("%lld",&w[i]); 51 for(int i=1;i<n;i++) d[i]=(d[i]+d[i-1])%mod;//前缀和 52 for(int i=n;i>1;i--) d[i]=d[i-1]; 53 d[1]=0; 54 built(1,1,n); 55 while(m--) 56 { 57 scanf("%lld%lld%lld",&x,&l,&r); 58 ll ans1,ans2,ans; 59 if(l==x&&r==x){ 60 printf("0 "); 61 continue; 62 } 63 if(l>x){ 64 ans=(ask2(1,l,r)-ask1(1,l,r)*d[x])%mod;//如解析所示 65 } 66 if(r<x){ 67 ans=(ask1(1,l,r)*d[x]-ask2(1,l,r))%mod; 68 } 69 if(l<=x&&x<=r){ 70 ans1=(ask1(1,l,x-1)*d[x]-ask2(1,l,x-1))%mod; 71 ans2=(ask2(1,x+1,r)-ask1(1,x+1,r)*d[x])%mod; 72 ans=(ans1+ans2)%mod; 73 } 74 printf("%lld ",(ans+3*mod)%mod); 75 } 76 return 0; 77 }
2019-05-15 18:56:20