CF1922C的题解

（一）

从 \(i\) 到 \(j\) 有两种走法，一种是用 \(a_j-a_i\) 的代价，一种是用 \(1\) 的代价，前提是 \(j\) 是 \(i\) 最近的。

显然如果符合条件选第二种。

先考虑从左向右走。（和从右向左相同）

考虑走到了节点 \(i\)，如果 \(a_{i+1}-a_{i}>a_{i}-a_{i-1}\)，那么花费 \(1\) 的代价向右走，否则花费 \(a_{i+1}-a_{i}\) 的代价向右走。

用类似于前缀和的方法统计，由于每一步用哪种与前面无关（肯定能选第二种就第二种），那么只用从左到右，从右到左都扫一遍即可。

\(ltor_{i}\) 表示从 \(1\) 走到 \(i\) 最少代价。

从 \(l\) 到 \(r\) 最少代价即为 \(ltor_{r}-ltor_{l}\)。

（二）

AC 代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,l,r,q,a[100010],ltor[100010],rtol[100010];
signed main(){
	scanf("%lld",&t);
	while(t--){
		scanf("%lld",&n);
		for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
		for(int i=2;i<=n;i++){
			if(a[i]-a[i-1]<=a[i-1]-a[i-2]||i==2)ltor[i]=ltor[i-1]+1;
			else ltor[i]=ltor[i-1]+a[i]-a[i-1];
		}
		for(int i=n-1;i>=1;i--){
			if(a[i+1]-a[i]<=a[i+2]-a[i+1]||i==n-1)rtol[i]=rtol[i+1]+1;
			else rtol[i]=rtol[i+1]+a[i+1]-a[i];
		}
		scanf("%lld",&q);
		while(q--){
			scanf("%lld%lld",&l,&r);
			if(l<r)printf("%lld\n",ltor[r]-ltor[l]);
			else printf("%lld\n",rtol[r]-rtol[l]);
		}
	}
	return 0;
}
```