https://codeforces.com/contest/1922/problem/C
题目大意
给出数轴上的 $n \ (2 \le n \le 10^5)$ 个点。$0 \le a_1 < a_2 < a_3 < \cdots < a_n \le 10^9$
从 $i$ 点直接走到另外一个点 $j$ 的花费为 $|a_i - a_j|$ 或当 $j$ 是 $i$ 与所有点之间距离最近的点时花费为 $1$。
给出 $m \ (1 \le m \le 10^5)$ 次询问。每次问从 $x_i$ 到 $y_i$ 的路径的最小花费是多少。
简要题解
观察，$x$ 的最近点总会是 $x - 1$ 或/和 $x + 1$。易证，假设 $x + k$ 为最近点，则 $a[x] < a[x + 1] < a[x + k]$ 则 $a[x + k] - a[x] > a[x + 1] - a[x]$，显然比 $a[x + 1]$ 劣。
考虑 $x < y$ 则如下方案总是最优的，$x$ -> $x + 1$ -> $x + 2$ -> … -> $y$。
证明：首先对于路径，我们总是可以不跳过相邻城市，因为假设从 $x -> z$ 是最优路径中的一段，将其分解为 $x$ -> $x + 1$ -> … -> $z$ 不会让结果变差。因此向反方向走总是没有意义的，我们总要走回到起点再向前走。
同理可证 $y > x$ 的情况。
注意到，$x$ 是 $y$ 的最近点，不一定 $y$ 是 $x$ 的最近点，所以从左向右和从右向左要准备两个前缀和。
复杂度
$T$：$O(n)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n; cin >> n;
vector<int> a(n);
for (int& i : a) cin >> i;
// 1 -> [0, 1]
// n - 1 -> [n - 2, n - 1]
vector<LL> suml(n), sumr(n);
for (int i = 1; i < n; i++) {
suml[i] = suml[i - 1] +
(i - 1 == 0 || a[i] - a[i - 1] <= a[i - 1] - a[i - 2] ? 1 : a[i] - a[i - 1]);
sumr[i] = sumr[i - 1] +
(i == n - 1 || a[i] - a[i - 1] <= a[i + 1] - a[i] ? 1 : a[i] - a[i - 1]);
}
int q; cin >> q;
int x, y;
for (int i = 0; i < q; i++) {
cin >> x >> y;
if (x < y) {
cout << (suml[y - 1] - suml[x - 1]) << '\n';
} else {
cout << (sumr[x - 1] - sumr[y - 1]) << '\n';
}
}
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] D. Berserk Monsters - Educational Codeforces Round 161 (Rated for Div. 2)