题目描述

难度分:$1300$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 10^5$，$m$之和$\leq 10^5$。

每组数据输入$n(2 \leq n \leq 10^5)$和长为$n$的严格递增数组$a(0 \leq a[i] \leq 10^9)$。

然后输入$m(1 \leq m \leq 10^5)$和$m$个询问，每个询问输入两个数$x$和$y$，范围$[1,n]$且$x \neq y$。

数轴上有$n$个点，点$i$的坐标为$a[i]$。有两种移动方式：

1. 从点$i$移动到离它最近的点，花费是$1$。保证每个点只有唯一的离它最近的点。

2. 从点$i$移动到点$j$，花费是$|a[i]-a[j]|$。

对于每个询问，输出从点$x$移动到点$y$的最小花费。

输入样例

1
5
0 8 12 15 20
5
1 4
1 5
3 4
3 2
5 1

输出样例

3
8
1
4
14

算法

前缀和+后缀和

预处理出$l2r$数组和$r2l$数组，$l2r[i]$表示$i$走到$i+1$所需的代价，这时候需要检查$i$和左右邻居的距离哪个小，如果$i$与$i+1$的距离更小，那$l2r[i]=1$，否则$l2r[i]=a[i+1]-a[i]$。$r2l$数组也是同理，只是$r2l[i]$表示$i$走到$i-1$所需的代价。

然后对$l2r$求后缀和$suf$，对$r2l$求前缀和$pre$就可以$O(1)$计算每个询问了。如果$x \lt y$，则答案为$suf[x]-suf[y]$，否则答案为$pre[x]-pre[y]$。

复杂度分析

时间复杂度

求$l2r$、$r2l$、$pre$和$suf$都是线性的时间复杂度，为$O(n)$。有了前后缀和数组$pre$和$suf$，每个$query$就可以$O(1)$求了。因此，整个算法的时间复杂度为$O(n+m)$。

空间复杂度

开辟了四个线性空间的数组$l2r$、$r2l$、$pre$和$suf$，额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;
int a[N], l2r[N], r2l[N], pre[N], suf[N];

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        int n;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        l2r[1] = 1;
        for(int i = 2; i < n; i++) {
            if(a[i + 1] - a[i] < a[i] - a[i - 1]) {
                l2r[i] = 1;
            }else {
                l2r[i] = a[i + 1] - a[i];
            }
        }
        for(int i = n - 1; i >= 1; i--) {
            suf[i] = suf[i + 1] + l2r[i];
        }
        r2l[n] = 1;
        for(int i = n - 1; i >= 1; i--) {
            if(a[i] - a[i - 1] < a[i + 1] - a[i]) {
                r2l[i] = 1;
            }else {
                r2l[i] = a[i] - a[i - 1];
            }
        }
        for(int i = 2; i <= n; i++) {
            pre[i] = pre[i - 1] + r2l[i];
        }
        int m;
        scanf("%d", &m);
        while(m--) {
            int x, y;
            scanf("%d%d", &x, &y);
            if(x < y) {
                printf("%d\n", suf[x] - suf[y]);
            }else {
                printf("%d\n", pre[x] - pre[y]);
            }
        }
    }
    return 0;
}