---
title: P3932 浮游大陆的68号岛
type: 题解
tags:
  - 信息竞赛题解
  - 前缀和
  - 数学
---

# P3932 浮游大陆的68号岛

## 题意

第二行 $n - 1$ 个数，第 $i$ 个数表示第 $i$ 个储物点与第 $i + 1$ 个储物点的距离

有 $n$ 个储物点，每个储物点 $i$ 有 $x$ 个东西，要运到储物点 $j$，代价为


$$x \times \mathrm{dist}( i , j )$$

`dist`就是仓库间的距离。

之后 $m$ 行每行三个数`x l r`

表示查询要把区间 $[l,r]$ 储物点的物品全部运到储物点x的花费

对于100%的数据 ,$ n , m \le 200000 ; a_i , b_i <= 2\cdot 10^9$

您的答案需要对19260817取模。

## 解法

首先把题意转换成数学形式化语言：

对于一次查询，我们的花费是：
$$
\sum^{r}_{i = l} \left | pre_i - pre_x \right | \times a_i
$$
其中 $pre_i$ 表示储物点 $1$ 到储物点 $i$ 的距离。

发现有绝对值，那么就需要我们对 $x$ 的大小进行分类讨论。

1. $x \le l$

此时 $pre_x \le pre_i$，所以直接去掉绝对值即可：
$$
\sum^{r}_{i = l} \left ( pre_i - pre_x \right ) \times a_i\\
= \sum^{r}_{i = l} pre_i \times a_i - pre_x \times \sum^{r}_{i = l} a_i\\
$$
我们设 $prea_i$ 是 $pre_i \times a_i$ 的前缀和，$aa_k$ 为 $\sum^{k}_{i = 1} a_i$

则式子变为：
$$
\left( prea_r - prea_{l - 1} \right) - pre_x \times \left( aa_r - aa_l - 1 \right)
$$
可以 $O(1)$ 计算。

2. $x \ge r$

与`1`的情况同理，可以得到计算式为：
$$
pre_x \times \left( aa_r - aa_{l - 1} \right) - \left( prea_r - prea_{l - 1} \right)
$$

3. $l < x < r$

答案可以看成：
$$
\sum^{x}_{i = l} \left( pre_x - pre_i \right) \times a_i + \sum^{r}_{i = x} \left( pre_i - pre_x \right) \times a_i
$$
化简后可以得到：
$$
\left( prea_x - prea_{l - 1} \right) + pre_x \times \left( aa_x - aa_{l - 1} \right) + \left( prea_r - prea_{x - 1} \right) + pre_x \times \left( aa_r - aa_{x - 1} \right)
$$
那么我们只要预处理出 $pre_i \times a_i$，$a_i$，$dis_i$，的前缀和就可以了。

## code:

```cpp
#include<iostream>
#include<algorithm>
using namespace std;
const int MOD = 19260817;
const int MAXN = 2e5 + 1;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
inline void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');return;}

int n,m;
int d[MAXN];
int a[MAXN];
long long prea[MAXN],pre[MAXN];
long long aaa[MAXN];
int xx,ll,rr;
int ans = 0;
int solve(int x,int l,int r){
	ans = 0;
	if(x <= l){
		ans = ((ans + prea[r] - prea[l - 1]) % MOD + MOD) % MOD;
		ans = (((ans - pre[x] * aaa[r]) % MOD + MOD) % MOD + pre[x] * aaa[l - 1]) % MOD;
	}else if(x >= r){
		ans = ((ans + pre[x] * (aaa[r] - aaa[l - 1])) % MOD + MOD) % MOD;
		ans = ((ans - (prea[r] - prea[l - 1])) % MOD + MOD) % MOD;
	}else{
		ans = ((ans + pre[x] * aaa[x] - pre[x] * aaa[l - 1] % MOD) + MOD) % MOD;
		ans = ((ans - (prea[x] - prea[l - 1])) % MOD + MOD) % MOD;
		
		ans = ((ans + prea[r] - prea[x - 1]) % MOD + MOD) % MOD;
		ans = ((((ans - pre[x] * aaa[r]) % MOD + MOD) + pre[x] * aaa[x - 1]) % MOD + MOD) % MOD;
	}
	return ans;
}
int i;
signed main(){
	n = read();m = read();
	for(i = 1;i < n;i++) d[i] = read(),d[i] %= MOD;
	for(i = 1;i <= n;i++) a[i] = read(),a[i] %= MOD;
	for(i = 1;i <= n;i++) aaa[i] = (aaa[i - 1] + a[i]) % MOD;
	for(i = 1;i <= n;i++) pre[i] = (pre[i - 1] + d[i - 1]) % MOD;
	for(i = 1;i <= n;i++) prea[i] = (prea[i - 1] + (pre[i] * a[i])) % MOD;
	for(i = 1;i <= m;i++){
		xx = read(),ll = read(),rr = read();
		write(solve(xx,ll,rr));
		printf("\n");
	}
	return 0;
}
```
