[已解决]求助洛谷P2880！

Ewan-Ahiouy

我的代码：

#include <bits/stdc++.h>
using namespace std;

int n, a[50010], q, l, r, zuida = -1, zuixiao = 1145141919;

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= q; i++) {
        cin >> l >> r;
        zuida = -1, zuixiao = 1145141919;
        for (int j = l; j <= r; j++) {
            zuida = max(zuida, a[j]);
            zuixiao = min(zuixiao, a[j]);
        }
        cout << zuida - zuixiao << endl;
    }

    return 0;
}

TLE QAQ，要如何优化呢？

题解都说用ST表，蒟蒻不会啊QAQ

有没有大佬解释一下ST表要怎么用啊

最佳答案

月排行榜 / 总排行榜

zhangjinxuan

2023-8-19 11:36:56

st表学的不精，待会儿给你ST板子。

ST大致思路好像就是，定义 f[ i][ j] 为 i ~ i+2^j-1 这个区间的最小值（其他运算也可以，但是有限制），然后求 i j 区间最小值就分两段（两段必须覆盖整个区间，可以重叠）求值即可。

这里的运算（假定运算符为@）必须让 A@A =A一定成立，加法不行，最大值可以，或运算，与运算也可以。

跳转到最佳答案楼层

isdkz

ST表是一种用于解决区间最值问题的数据结构。它可以在O(nlogn)的预处理时间内，回答任意区间的最值查询。

在你的代码中，你使用了两个循环来遍历查询区间内的元素，这样的时间复杂度是O(q*(r-l+1))，当数据规模较大时会超时。所以可以使用ST表来优化。

ST表的构建过程如下：
1. 首先，我们需要创建一个二维数组dp，其中dp[ i][j]表示从位置i开始，长度为2^j的区间内的最大值（或最小值，根据问题要求而定）。
2. 初始化dp数组的第一列，即dp[ i][0] = a[ i]。
3. 然后，根据以下递推关系计算dp数组的其他列：
   · 如果2^j > n-i+1，则dp[ i][j] = dp[ i][j-1]。
   · 否则，dp[ i][j] = max(dp[ i][j-1], dp[i+2^(j-1)][j-1])。

构建完成后，我们可以通过查询dp数组来回答任意区间的最值查询。具体步骤如下：
1. 计算区间长度len = r - l + 1。
2. 找到最大的k，使得2^k <= len。
3. 查询结果为max(dp[l][k], dp[r-2^k+1][k])。

下面是应用ST表优化后的代码：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50010;
const int MAXLOG = 20;

int n, a[MAXN], q, l, r;
int dp[MAXN][MAXLOG];

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

    // 构建ST表
    for (int i = 1; i <= n; i++) {
        dp[ i][0] = a[ i];
    }
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            dp[ i][j] = max(dp[ i][j-1], dp[i+(1<<(j-1))][j-1]);
        }
    }

    // 查询区间最值
    for (int i = 1; i <= q; i++) {
        cin >> l >> r;
        int len = r - l + 1;
        int k = log2(len);
        int ans = max(dp[l][k], dp[r-(1<<k)+1][k]);
        cout << ans << endl;
    }

    return 0;
}

这样，你的代码就能通过洛谷P2880的测试了。希望能帮到你！

陶远航

洛谷 P2880 题目是求区间最大值与最小值的差的最小值。你提供的代码使用了暴力法，对每个查询的区间进行遍历，时间复杂度较高。

ST 表（Sparse Table）是一种用于快速求解区间最大值或最小值的数据结构，利用动态规划的思想，在预处理阶段计算出所有可能区间的最大值或最小值，并存储在一个二维数组中。这样，在查询时可以通过查表从中取出结果，达到快速查询的目的。

以下是使用 ST 表来优化的示例代码：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50010;
const int K = 20;  // ST 表的最大层数

int n, a[MAXN], st[MAXN][K+1];

// 预处理 ST 表
void initST() {
    for (int i = 1; i <= n; i++) {
        st[ i][0] = a[ i];
    }
    for (int j = 1; j <= K; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[ i][j] = max(st[ i][j-1], st[i + (1 << (j-1))][j-1]);  // 可根据题意改变操作符
        }
    }
}

// 查询区间 [l, r] 的最大值
int queryST(int l, int r) {
    int k = log2(r - l + 1);  // 通过对数函数求出区间长度对应 ST 表的层数
    return max(st[l][k], st[r - (1 << k) + 1][k]);  // 可根据题意改变操作符
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[ i];
    }
    initST();  // 预处理 ST 表

    int q, l, r;
    cin >> q;
    while (q--) {
        cin >> l >> r;
        int zuida = queryST(l, r);
        int zuixiao = *min_element(a+l, a+r+1);
        cout << zuida - zuixiao << endl;
    }

    return 0;
}

这段代码使用了 ST 表来预处理数组，通过动态规划计算出所有区间的最大值，然后在查询时快速取出结果。注意，这里用到了 max() 函数和 min_element() 函数，可以根据题目要求进行修改。

希望这个示例能够帮助你理解 ST 表的使用方法。如果还有其他问题，请随时提问。
如果问题已经解决，请设置最佳答案

Ewan-Ahiouy

@欧拉计划 @sfqxx @zhangjinxuan

zhangjinxuan

st表学的不精，待会儿给你ST板子。

ST大致思路好像就是，定义 f[ i][ j] 为 i ~ i+2^j-1 这个区间的最小值（其他运算也可以，但是有限制），然后求 i j 区间最小值就分两段（两段必须覆盖整个区间，可以重叠）求值即可。

这里的运算（假定运算符为@）必须让 A@A =A一定成立，加法不行，最大值可以，或运算，与运算也可以。

zhangjinxuan

st 求解 rmq 问题：

int main(){
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) {
        输入  ai
        f[0][i] = a[i];
    }
    for (int j = 1; j <= 20; ++j) {
                for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
                        f[j][i] = max(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);
                }
        }
    for (int i = 1; i <= q; i++) {
        读入 l,r
        if (l > r) swap(l, r);
        unsigned int x = __lg(r - l + 1);
        输出 max(f[x][l], f[x][r - (1 << x) + 1]);
    }
}

也不需要倍增呃

sfqxx

zhangjinxuan 发表于 2023-8-19 11:36
st表学的不精，待会儿给你ST板子。

ST大致思路好像就是，定义 f[ i][ j] 为 i ~ i+2^j-1 这个区间的最小 ...

nb

sfqxx

zhangjinxuan 发表于 2023-8-19 11:41
st 求解 rmq 问题：
也不需要倍增呃

%%%%

sfqxx

这道题本来是道蓝题（提高+/省选-），因为可以用ST表降黄了，神奇

Ewan-Ahiouy

sfqxx 发表于 2023-8-19 12:27
这道题本来是道蓝题（提高+/省选-），因为可以用ST表降黄了，神奇

高山

不会？没关系的，查看题解抄下来，还送棕名认证！

Ewan-Ahiouy

高山 发表于 2023-8-19 17:25
不会？没关系的，查看题解抄下来，还送棕名认证！

高山

Ewan-Ahiouy 发表于 2023-8-19 17:44

赶紧做起来吧，越快越好，记得发帖@管理员，我正准备努力成为一个呢（你知道我 条件远远不够，蓝勾红名一个都没打成，之前抄题解还没被人发现

Ewan-Ahiouy

高山 发表于 2023-8-19 17:45
赶紧做起来吧，越快越好，记得发帖@管理员，我正准备努力成为一个呢（你知道我 条件远远不够，蓝勾红名一 ...

你是不是神经？

高山

Ewan-Ahiouy 发表于 2023-8-19 17:52
你是不是神经？

神经元处理系统？

sfqxx

#include <bits/stdc++.h>
using namespace std;

const int maxn = 50010;
int n, h[maxn], q, l, r, log_2[maxn], rmax[maxn][18], rmin[maxn][18];

void init() {
    for (int i = 1; i <= n; i++) rmax[i][0] = rmin[i][0] = h[i];
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 1; i <= n - (1 << j) + 1; i++) {
            rmax[i][j] = max(rmax[i][j - 1], rmax[i + (1 << j - 1)][j - 1]);
            rmin[i][j] = min(rmin[i][j - 1], rmin[i + (1 << j - 1)][j - 1]);
        }
}

int mymax(int l, int r) {
    int x = log_2[r - l + 1];
    return max(rmax[l][x], rmax[r - (1 << x) + 1][x]);
}

int mymin(int l, int r) {
    int x = log_2[r - l + 1];
    return min(rmin[l][x], rmin[r - (1 << x) + 1][x]);
}

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 2; i <= n; i++) log_2[i] = log_2[i >> 1] + 1;
    init();
    while (q--) {
        cin >> l >> r;
        cout << mymax(l, r) - mymin(l, r) << endl;
    }

    return 0;
}

你不是过了吗？

Ewan-Ahiouy

sfqxx 发表于 2023-8-20 13:24
你不是过了吗？

是啊，抄课本的

sfqxx

Ewan-Ahiouy 发表于 2023-8-20 13:29
是啊，抄课本的

给我最佳吧

洛谷基础赛第二题我竟然自己写出来了。

Ewan-Ahiouy

sfqxx 发表于 2023-8-20 13:31
给我最佳吧

洛谷基础赛第二题我竟然自己写出来了。

厉害！

sfqxx

Ewan-Ahiouy 发表于 2023-8-20 13:41
厉害！

你知道你为什么一直WA吗？

因为输出后需要加end=" "哈哈