求助洛谷P2880！
我的代码：#include <bits/stdc++.h>
using namespace std;
int n, a, q, l, r, zuida = -1, zuixiao = 1145141919;
int main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a;
}
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);
zuixiao = min(zuixiao, a);
}
cout << zuida - zuixiao << endl;
}
return 0;
}
TLE QAQ，要如何优化呢？
题解都说用ST表，蒟蒻不会啊QAQ
有没有大佬解释一下ST表要怎么用啊{:10_266:}
ST表是一种用于解决区间最值问题的数据结构。它可以在O(nlogn)的预处理时间内，回答任意区间的最值查询。
在你的代码中，你使用了两个循环来遍历查询区间内的元素，这样的时间复杂度是O(q*(r-l+1))，当数据规模较大时会超时。所以可以使用ST表来优化。
ST表的构建过程如下：
1. 首先，我们需要创建一个二维数组dp，其中dp[ i]表示从位置i开始，长度为2^j的区间内的最大值（或最小值，根据问题要求而定）。
2. 初始化dp数组的第一列，即dp[ i] = a[ i]。
3. 然后，根据以下递推关系计算dp数组的其他列：
· 如果2^j > n-i+1，则dp[ i] = dp[ i]。
· 否则，dp[ i] = max(dp[ i], dp)。
构建完成后，我们可以通过查询dp数组来回答任意区间的最值查询。具体步骤如下：
1. 计算区间长度len = r - l + 1。
2. 找到最大的k，使得2^k <= len。
3. 查询结果为max(dp, dp)。
下面是应用ST表优化后的代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50010;
const int MAXLOG = 20;
int n, a, q, l, r;
int dp;
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] = a[ i];
}
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
dp[ i] = max(dp[ i], dp);
}
}
// 查询区间最值
for (int i = 1; i <= q; i++) {
cin >> l >> r;
int len = r - l + 1;
int k = log2(len);
int ans = max(dp, dp);
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, st;
// 预处理 ST 表
void initST() {
for (int i = 1; i <= n; i++) {
st[ i] = a[ i];
}
for (int j = 1; j <= K; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
st[ i] = max(st[ i], st);// 可根据题意改变操作符
}
}
}
// 查询区间 的最大值
int queryST(int l, int r) {
int k = log2(r - l + 1);// 通过对数函数求出区间长度对应 ST 表的层数
return max(st, st);// 可根据题意改变操作符
}
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 表的使用方法。如果还有其他问题，请随时提问。
如果问题已经解决，请设置最佳答案 @欧拉计划 @sfqxx @zhangjinxuan {:10_266:} 本帖最后由 zhangjinxuan 于 2023-8-26 19:52 编辑
st表学的不精，待会儿给你ST板子。
ST大致思路好像就是，定义 f[ i][ j] 为 i ~ i+2^j-1 这个区间的最小值（其他运算也可以，但是有限制），然后求 i j 区间最小值就分两段（两段必须覆盖整个区间，可以重叠）求值即可。
这里的运算（假定运算符为@）必须让 A@A =A一定成立，加法不行，最大值可以，或运算，与运算也可以。
st 求解 rmq 问题：
int main(){
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
输入ai
f = a;
}
for (int j = 1; j <= 20; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
f = max(f, f);
}
}
for (int i = 1; i <= q; i++) {
读入 l,r
if (l > r) swap(l, r);
unsigned int x = __lg(r - l + 1);
输出 max(f, f);
}
}也不需要倍增呃 zhangjinxuan 发表于 2023-8-19 11:36
st表学的不精，待会儿给你ST板子。
ST大致思路好像就是，定义 f[ i][ j] 为 i ~ i+2^j-1 这个区间的最小 ...
nb zhangjinxuan 发表于 2023-8-19 11:41
st 求解 rmq 问题：
也不需要倍增呃
%%%% 这道题本来是道蓝题（提高+/省选-），因为可以用ST表降黄了，神奇
sfqxx 发表于 2023-8-19 12:27
这道题本来是道蓝题（提高+/省选-），因为可以用ST表降黄了，神奇
{:10_266:} 不会？没关系的，查看题解抄下来，还送棕名认证！ 高山 发表于 2023-8-19 17:25
不会？没关系的，查看题解抄下来，还送棕名认证！
{:10_249:} Ewan-Ahiouy 发表于 2023-8-19 17:44
赶紧做起来吧，越快越好，记得发帖@管理员，我正准备努力成为一个呢（你知道我 条件远远不够，蓝勾红名一个都没打成，之前抄题解还没被人发现 高山 发表于 2023-8-19 17:45
赶紧做起来吧，越快越好，记得发帖@管理员，我正准备努力成为一个呢（你知道我 条件远远不够，蓝勾红名一 ...
你是不是神经？ Ewan-Ahiouy 发表于 2023-8-19 17:52
你是不是神经？
神经元处理系统？ #include <bits/stdc++.h>
using namespace std;
const int maxn = 50010;
int n, h, q, l, r, log_2, rmax, rmin;
void init() {
for (int i = 1; i <= n; i++) rmax = rmin = h;
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i <= n - (1 << j) + 1; i++) {
rmax = max(rmax, rmax);
rmin = min(rmin, rmin);
}
}
int mymax(int l, int r) {
int x = log_2;
return max(rmax, rmax);
}
int mymin(int l, int r) {
int x = log_2;
return min(rmin, rmin);
}
int main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> h;
for (int i = 2; i <= n; i++) log_2 = log_2 + 1;
init();
while (q--) {
cin >> l >> r;
cout << mymax(l, r) - mymin(l, r) << endl;
}
return 0;
}
你不是过了吗？ sfqxx 发表于 2023-8-20 13:24
你不是过了吗？
是啊，抄课本的 Ewan-Ahiouy 发表于 2023-8-20 13:29
是啊，抄课本的
给我最佳吧
洛谷基础赛第二题我竟然自己写出来了。 sfqxx 发表于 2023-8-20 13:31
给我最佳吧
洛谷基础赛第二题我竟然自己写出来了。
{:10_257:}厉害！ Ewan-Ahiouy 发表于 2023-8-20 13:41
厉害！
你知道你为什么一直WA吗？
因为输出后需要加end=" "哈哈
页:
[1]
2