题目

命运不止天注定。

小J和小R最近迷恋上了MBTI，每天都在问别人是什么MBTI。

小J："我是ENFP，你MBTI是什么呀。"

小R："我是ISTJ，咱俩真是一点对不上啊。"

他们企图通过MBTI来判断一个人的性格。但是由于小J和小R记性不好总是忘记别人的MBTI，又总是想问别人，又担心自己不礼貌，于是小R想了个办法，针对一排人，每个人手上都拿了两个数A和B，想要通过这些数字来计算每个人的"命运值"。由于在不同的人旁边命运有可能会发生变化，于是小R定义每个人的命运值是从他开始往前B个人手中A的最大值和最小值的乘积，现在小R想要小J帮忙计算每个人的命运值，但是由于小J正在研究MBTI，所以希望你能够来帮助他！

现给出一个序列A和一个序列B，对于序列中的第i个人而言，定义他的命运值 = min(A[i], A[i−1]……A[i−B[i]+1]) × max(A[i], A[i−1]……A[i−B[i]+1])。现在请你告诉小J和小R序列中的每个人的命运值是多少。

输入：第一行一个整数 N；接下来一行 N 个整数，分别表示 A[i]；接下来一行 N 个整数，分别表示 B[i]。
输出：输出 N 行，依次表示第 i 个位置的命运值。

样例1：

输入

3
1 2 5
1 2 2

输出

1
2
10

样例2：

输入

5
1 2 3 4 5
1 2 1 2 3

输出

1
2
9
12
15

提示：对于 100% 的数据，保证 n≤100000，1≤B[i]≤i，|A[i]|≤109。

思路

每个位置 i 要查询区间 [i−B[i]+1, i] 的最小值和最大值，B[i] 各不相同，是变长区间 RMQ 问题。用稀疏表（Sparse Table）预处理：st_min[k][i] 和 st_max[k][i] 分别存储从 i 开始长度为 2k 的区间最值，利用区间可重叠的性质，查询时取 k = ⌊log₂(r−l+1)⌋，用两段长度为 2k 的区间覆盖 [l, r] 即可 O(1) 完成。最终输出 min × max。

C++ · p58.cpp 
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int LOG = 17;  // 2^17 = 131072 > 1e5

int n;
long long A[MAXN];
int B[MAXN];
long long st_min[LOG][MAXN], st_max[LOG][MAXN];

// 构建稀疏表：st[k][i] = 区间 [i, i+2^k-1] 的最值
void build() {
    for (int i = 0; i < n; ++i) {
        st_min[0][i] = A[i];
        st_max[0][i] = A[i];
    }
    for (int k = 1; (1 << k) <= n; ++k)
        for (int i = 0; i + (1 << k) - 1 < n; ++i) {
            st_min[k][i] = min(st_min[k-1][i], st_min[k-1][i + (1 << (k-1))]);
            st_max[k][i] = max(st_max[k-1][i], st_max[k-1][i + (1 << (k-1))]);
        }
}

// 查询 [l, r] 最小值：两段 2^k 区间重叠覆盖
long long query_min(int l, int r) {
    int k = log2(r - l + 1);
    return min(st_min[k][l], st_min[k][r - (1 << k) + 1]);
}

// 查询 [l, r] 最大值
long long query_max(int l, int r) {
    int k = log2(r - l + 1);
    return max(st_max[k][l], st_max[k][r - (1 << k) + 1]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) cin >> A[i];
    for (int i = 0; i < n; ++i) cin >> B[i];

    build();

    for (int i = 0; i < n; ++i) {
        int l = i - B[i] + 1;
        int r = i;
        long long mn = query_min(l, r);
        long long mx = query_max(l, r);
        cout << mn * mx << '\n';
    }
    return 0;
}

复杂度分析

  • 时间复杂度：O(n log n) 预处理，O(1) 每次查询
  • 空间复杂度：O(n log n)，稀疏表两张
今日感受

这题好难。稀疏表的核心是"区间可重叠"——min 和 max 不怕重复计算，两段 2k 长的区间合起来盖住整个查询区间，O(1) 就搞定了。想出这个是最难的一步。

← 返回菜鸟的coding