p1816

问题分析

题目要求处理多个区间最小值查询。给定一个包含 个账目金额的序列，以及 个查询，每个查询指定一个区间 ，需要快速返回该区间内的最小值。由于查询次数 可能很大，我们需要一个高效的算法，确保在合理时间内完成所有查询。

算法选择：稀疏表（Sparse Table）

• 适用场景：静态数组（无修改操作）的区间最值查询（RMQ）。
• 时间复杂度：
  • 预处理：
  • 单次查询：
• 空间复杂度：
• 核心思想：
  1. 预处理：构建一个二维数组 dp，其中 dp[i][j] 表示从位置 开始、长度为 的区间的最小值。
  2. 查询：对于任意区间 ，将其拆分为两个长度为 的重叠子区间（），取这两个子区间的最小值作为结果。

优化细节

1. 预处理 表：避免重复计算对数，预先计算 到 的 值。
2. 0-indexed 转换：题目中账目编号从 1 开始，代码中转换为 0-indexed 数组下标。
3. 快速 I/O：使用 scanf 和 printf 加速输入输出，避免超时。

代码实现

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

int main() {
    int m, n;
    scanf("%d %d", &m, &n);
    
    vector<int> arr(m);
    for (int i = 0; i < m; i++) {
        scanf("%d", &arr[i]);
    }
    
    // 预处理 log2_table: log2_table[i] = floor(log2(i))
    vector<int> log2_table(m + 1, 0);
    for (int i = 2; i <= m; i++) {
        log2_table[i] = log2_table[i / 2] + 1;
    }
    
    // 计算最大幂次 k
    int k = log2_table[m] + 1;
    
    // 构建稀疏表 dp
    vector<vector<int>> dp(m, vector<int>(k));
    for (int i = 0; i < m; i++) {
        dp[i][0] = arr[i];
    }
    
    for (int j = 1; j < k; j++) {
        for (int i = 0; i + (1 << j) <= m; i++) {
            dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
        }
    }
    
    vector<int> ans;
    for (int i = 0; i < n; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        // 转换为0-indexed
        int l = a - 1, r = b - 1;
        int len = r - l + 1;
        int j = log2_table[len];
        int res = min(dp[l][j], dp[r - (1 << j) + 1][j]);
        ans.push_back(res);
    }
    
    // 输出所有答案，空格分隔
    for (int i = 0; i < ans.size(); i++) {
        if (i > 0) printf(" ");
        printf("%d", ans[i]);
    }
    printf("\n");
    
    return 0;
}

复杂度分析

• 时间：
  • 预处理 表：。
  • 构建稀疏表：。
  • 处理 个查询：。
• 空间： 存储稀疏表。

注意事项

• 边界处理：确保区间 有效（），题目保证 。
• 效率：当 时，，空间占用约 个整数，符合内存限制。
• 重叠区间：虽然子区间重叠，但取最小值操作不受影响，结果正确。