p2880

本题要求处理多个区间查询，每次查询需要快速得到区间内最大值与最小值的差值。由于数据规模较大（n ≤ 5×10⁴, q ≤ 1.8×10⁵），需要使用高效的区间查询算法。这里采用 ST表（Sparse Table） 算法，其特点是在 O(n log n) 时间内预处理，之后每个查询可在 O(1) 时间内完成，非常适合本题的多次查询需求。

ST表原理

ST表的核心思想是倍增和动态规划：

• 预处理：构建两个二维数组 max_st 和 min_st，其中：
  • max_st[k][i] 表示区间 [i, i + 2ᵏ - 1] 中的最大值。
  • min_st[k][i] 表示区间 [i, i + 2ᵏ - 1] 中的最小值。
• 状态转移方程：
  • max_st[k][i] = max(max_st[k-1][i], max_st[k-1][i + 2^{k-1}])
  • min_st[k][i] = min(min_st[k-1][i], min_st[k-1][i + 2^{k-1}])
• 查询：对于区间 [l, r]，令 k = floor(log2(r - l + 1))，则：
  • 最大值 = max(max_st[k][l], max_st[k][r - 2^k + 1])
  • 最小值 = min(min_st[k][l], min_st[k][r - 2^k + 1])
  • 答案 = 最大值 - 最小值

步骤

1. 输入处理：
   • 读取牛的数量 n 和查询次数 q。
   • 读取每头牛的身高 h[1..n]。
2. 预处理 log2 数组：
   • 构建数组 log_table，其中 log_table[i] = floor(log2(i))，用于快速计算区间长度对应的k值。
3. 构建ST表：
   • 初始化 k=0 时的ST表（即单个元素）。
   • 递推计算 k=1 到 k_max（k_max = log_table[n]）的ST表。
4. 处理查询：
   • 对于每个查询 [a, b]，调整区间为 [l, r]（l = min(a, b), r = max(a, b)）。
   • 计算 k = log_table[r - l + 1]。
   • 通过ST表查询区间最大值和最小值，输出差值。

复杂度分析

• 预处理：O(n log n)，其中 log n ≈ 16（n=50000 时）。
• 查询：O(1) 每次，总 O(q)。
• 总复杂度：O(n log n + q)，可高效处理最大规模数据。

代码实现

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAXN = 50010;
const int MAXK = 17; // 2^16 = 65536 > 50000

int n, q;
int h[MAXN];
int log_table[MAXN];
int max_st[MAXK][MAXN];
int min_st[MAXK][MAXN];

void build_st() {
    // 初始化 k=0
    for (int i = 1; i <= n; i++) {
        max_st[0][i] = h[i];
        min_st[0][i] = h[i];
    }

    // 预处理 log_table
    log_table[1] = 0;
    for (int i = 2; i <= n; i++) {
        log_table[i] = log_table[i / 2] + 1;
    }

    int k_max = log_table[n];
    // 递推构建ST表
    for (int k = 1; k <= k_max; k++) {
        int step = 1 << (k - 1); // 2^(k-1)
        for (int i = 1; i + (1 << k) - 1 <= n; i++) {
            max_st[k][i] = max(max_st[k - 1][i], max_st[k - 1][i + step]);
            min_st[k][i] = min(min_st[k - 1][i], min_st[k - 1][i + step]);
        }
    }
}

int query(int l, int r) {
    int len = r - l + 1;
    int k = log_table[len];
    int max_val = max(max_st[k][l], max_st[k][r - (1 << k) + 1]);
    int min_val = min(min_st[k][l], min_st[k][r - (1 << k) + 1]);
    return max_val - min_val;
}

int main() {
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &h[i]);
    }

    build_st();

    while (q--) {
        int a, b;
        scanf("%d %d", &a, &b);
        int l = min(a, b);
        int r = max(a, b);
        printf("%d\n", query(l, r));
    }

    return 0;
}