题目分析

本题要求我们在给定的数组中，计算多个查询区间的“陡峭值”。每个查询给定一个区间 [l, r]，我们需要计算这个区间的陡峭值，陡峭值定义为相邻元素之差的绝对值之和。

思路解析

1. 陡峭值的定义

对于一个数组 a 来说，陡峭值是计算数组相邻元素之间差的绝对值之和：

|a[2] - a[1]| + |a[3] - a[2]| + ... + |a[r] - a[r-1]|

举个例子，假设数组为 [1, 4, 2, 3, 4]，我们要计算陡峭值时，只需要关注相邻元素的差的绝对值，得到以下计算：

|4 - 1| + |2 - 4| + |3 - 2| + |4 - 3| = 3 + 2 + 1 + 1 = 7

2. 如何高效计算查询区间的陡峭值？

对于每个查询 [l, r]，我们需要计算的是区间 [l, r] 中的相邻元素差的绝对值之和。因此，暴力方法就是从 l 到 r 遍历，计算每个相邻元素差的绝对值。但这种方法的时间复杂度是 O(n) 对每个查询都进行计算，总的时间复杂度是 O(n * q)，当 n 和 q 很大时，这种做法就不行了。

为了优化这个问题，我们可以考虑以下方式：

3. 预处理

对于所有相邻元素的差的绝对值，我们可以通过预处理计算出一个前缀和数组 prefix。定义 prefix[i] 表示数组从 a[1] 到 a[i] 的陡峭值之和，即：

prefix[i] = |a[i] - a[i-1]| + |a[i-1] - a[i-2]| + ... + |a[2] - a[1]|

这样，对于任意查询 [l, r]，我们可以通过差分法快速得到该区间的陡峭值：

result = prefix[r-1] - prefix[l-1]

4. 总结

1. 通过预处理计算 prefix 数组，时间复杂度为 O(n)。
2. 每个查询通过前缀和求解，时间复杂度为 O(1)。
3. 总的时间复杂度为 O(n + q)，非常高效。

三、代码实现

Python代码

n = int(input())  # 数组长度
a = list(map(int, input().split()))  # 数组元素
q = int(input())  # 查询次数

# 计算前缀和
prefix = [0] * n
for i in range(1, n):
    prefix[i] = prefix[i - 1] + abs(a[i] - a[i - 1])

# 处理每个查询
for _ in range(q):
    l, r = map(int, input().split())
    # 查询的结果是区间 [l, r] 的陡峭值，使用前缀和计算
    print(prefix[r - 1] - prefix[l - 1])

Java代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 输入
        int n = sc.nextInt(); // 数组长度
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int q = sc.nextInt(); // 查询次数

        // 计算前缀和
        long[] prefix = new long[n];
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + Math.abs(a[i] - a[i - 1]);
        }

        // 处理每个查询
        for (int i = 0; i < q; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            System.out.println(prefix[r - 1] - prefix[l - 1]);
        }

        sc.close();
    }
}

C++代码

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int q;
    cin >> q;

    // 计算前缀和
    vector<long long> prefix(n, 0);
    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] + abs(a[i] - a[i - 1]);
    }

    // 处理每个查询
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        cout << prefix[r - 1] - prefix[l - 1] << endl;
    }

    return 0;
}

题目内容

定义一个数组的的陡峭值为：相邻两个元素之差的绝对值之和。

现在小红拿到了一个数组，她有多次询问，每次查询一段连续子数组的陡峭值。你能帮帮她吗?

连续子数组为从原数组中，连续的选择一段元素(可以全选、可以不选)得到的新数组。

输入描述

第一行输入一个正整数$n$，代表数组长度。

第二行输入n个正整数$a_i$，代表小红拿到的数组。

第三行输入一个正整数$q$，代表询问次数。

接下来的$q$行，每行输入两个正整数$l,r$，代表一次询问。

$1≤n,q≤10^5$

$1≤a_i≤10^9$

$1≤l≤r≤n$

输出描述

输出$q$行，每行输出一个正整数，代表查询的结果。

样例1

输入

5
1 4 2 3 4
3
1 1
2 4
1 5

输出

0
3
7