zPatronus's blog

luoguP3932 浮游大陆的68号岛

Posted on Edited on

题目

开四个数组：

$lcnt[i]$记录仓库i左边（不包括i）共有多少物品 $rcnt[i]$记录仓库i右边（不包括i）共有多少物品 $lcost[i]$记录将仓库i左边的所有物品移到仓库i所需的代价 $rcost[i]$记录将仓库i右边的所有物品移到仓库i所需的代价。

$lcnt[i]$和$rcnt[i]$很好算，考虑如何O(n)计算$lcost[]$和$rcost[]​$。

以$lcost[]$为例

考虑新加入一个仓库。假设为6。

编号(i) 1 2 3 4 5 6
$lcnt[i]$ 0 4 5 6 8 9

把1-5号仓库的所有物品移到6号仓库等价于把1-4号仓库的所有物品移到5号仓库，然后把5号仓库里的所有东西移到6号仓库。

也就是$lcost[i]=lcost[i-1]+lcnt[i]·dis(i-1,i)$

$rcost[]$也可以如法炮制

考虑对于一个询问$l..r$

image

一定是形如这样的（或者在x的右边；或者包括了x，包括x时可以分成两段分开计算）

把$l..r$的所有物品移到x等价于把r左边所有物品移到r，然后把r仓库的所有东西移到x，减去把l左边所有东西移到l，然后把l仓库的所有东西移到x

也就是$cost(l,r)=lcnt[r+1]·(po[x]-po[r])+lcost[r]-lcost[l]-lcnt[l]·(po[x]-po[l])$

$l..r$在x的右边也可以如法炮制

code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
#define ll long long
#define N 200010
#define mo 19260817
#define md(a) (((a)%mo+mo)%mo)
#define mem(a,b) memset(a,b,sizeof(a))
#define fsb(a,b,c) for(ll a=b;a<=(c);a++)
#define fbs(a,b,c) for(ll a=b;a>=(c);a--)
using namespace std;
ll n,m,po[N],a[N],lcnt[N],rcnt[N],lcost[N],rcost[N],x,l,r;
template<typename qw>inline void rll(qw &x){
 x=0;qw f=1;char c=getchar();
 while(!isdigit(c))f=c=='-'?-1:f,c=getchar();
 while(isdigit(c))x=x*10+c-'0',c=getchar();
 x*=f;
}
int main(){
// freopen("3932_1.in","r",stdin);freopen("3932.out","w",stdout);
 rll(n);rll(m);po[1]=0;
 fsb(i,2,n){
  rll(po[i]);po[i]+=po[i-1];po[i]=md(po[i]);
 }
 mem(a,0);fsb(i,1,n)rll(a[i]);
 mem(lcnt,0);mem(rcnt,0);
 fsb(i,1,n){
  lcnt[i]=lcnt[i-1]+a[i-1];lcnt[i]=md(lcnt[i]);
 }
 fbs(i,n,1){
  rcnt[i]=rcnt[i+1]+a[i+1];rcnt[i]=md(rcnt[i]);
 }
 mem(lcost,0);mem(rcost,0);
 fsb(i,2,n){
  lcost[i]=md(lcost[i-1]+lcnt[i]*(po[i]-po[i-1]));
 }
// fsb(i,1,n)printf("%10lld %lld %lld\n",i,lcnt[i],rcnt[i]);
 fbs(i,n-1,1){
  rcost[i]=md(rcost[i+1]+rcnt[i]*(po[i+1]-po[i]));
 }
 fsb(i,1,m){
  rll(x);rll(l);rll(r);
  l=l==x?l+1:l;
  r=r==x?r-1:r;
  if(l>r){
   puts("0");continue;
  }
  ll ans=0;
  if(r<x){
   ans=md(lcnt[r+1]*(po[x]-po[r])+lcost[r]-lcost[l]-lcnt[l]*(po[x]-po[l]));
  }
  if(l>x){
   ans=md(rcnt[l-1]*(po[l]-po[x])+rcost[l]-rcost[r]-rcnt[r]*(po[r]-po[x]));
  }
  if(l<x&&r>x){
   ans=md(lcnt[x]*(po[x]-po[x-1])+lcost[x-1]-lcost[l]-lcnt[l]*(po[x]-po[l]));
   ans+=md(rcnt[x]*(po[x+1]-po[x])+rcost[x+1]-rcost[r]-rcnt[r]*(po[r]-po[x]));
   ans=md(ans);
  }
  printf("%lld\n",ans);
 }
 return 0;
}

注意：数字有点大，及时%。