[已解决]求助洛谷P2880！

Ewan-Ahiouy

我的代码：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int n, a[50010], q, l, r, zuida = -1, zuixiao = 1145141919;
   
5. 
   
6. int main() {
   
7.     cin >> n >> q;
   
8.     for (int i = 1; i <= n; i++) {
   
9.         cin >> a[i];
   
10.     }
    
11.     for (int i = 1; i <= q; i++) {
    
12.         cin >> l >> r;
    
13.         zuida = -1, zuixiao = 1145141919;
    
14.         for (int j = l; j <= r; j++) {
    
15.             zuida = max(zuida, a[j]);
    
16.             zuixiao = min(zuixiao, a[j]);
    
17.         }
    
18.         cout << zuida - zuixiao << endl;
    
19.     }
    
20. 
    
21.     return 0;
    
22. }

复制代码

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表优化后的代码：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int MAXN = 50010;
   
5. const int MAXLOG = 20;
   
6. 
   
7. int n, a[MAXN], q, l, r;
   
8. int dp[MAXN][MAXLOG];
   
9. 
   
10. int main() {
    
11.     cin >> n >> q;
    
12.     for (int i = 1; i <= n; i++) {
    
13.         cin >> a[ i];
    
14.     }
    
15. 
    
16.     // 构建ST表
    
17.     for (int i = 1; i <= n; i++) {
    
18.         dp[ i][0] = a[ i];
    
19.     }
    
20.     for (int j = 1; (1 << j) <= n; j++) {
    
21.         for (int i = 1; i + (1 << j) - 1 <= n; i++) {
    
22.             dp[ i][j] = max(dp[ i][j-1], dp[i+(1<<(j-1))][j-1]);
    
23.         }
    
24.     }
    
25. 
    
26.     // 查询区间最值
    
27.     for (int i = 1; i <= q; i++) {
    
28.         cin >> l >> r;
    
29.         int len = r - l + 1;
    
30.         int k = log2(len);
    
31.         int ans = max(dp[l][k], dp[r-(1<<k)+1][k]);
    
32.         cout << ans << endl;
    
33.     }
    
34. 
    
35.     return 0;
    
36. }
    

复制代码

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

陶远航

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

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

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

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int MAXN = 50010;
   
5. const int K = 20;  // ST 表的最大层数
   
6. 
   
7. int n, a[MAXN], st[MAXN][K+1];
   
8. 
   
9. // 预处理 ST 表
   
10. void initST() {
    
11.     for (int i = 1; i <= n; i++) {
    
12.         st[ i][0] = a[ i];
    
13.     }
    
14.     for (int j = 1; j <= K; j++) {
    
15.         for (int i = 1; i + (1 << j) - 1 <= n; i++) {
    
16.             st[ i][j] = max(st[ i][j-1], st[i + (1 << (j-1))][j-1]);  // 可根据题意改变操作符
    
17.         }
    
18.     }
    
19. }
    
20. 
    
21. // 查询区间 [l, r] 的最大值
    
22. int queryST(int l, int r) {
    
23.     int k = log2(r - l + 1);  // 通过对数函数求出区间长度对应 ST 表的层数
    
24.     return max(st[l][k], st[r - (1 << k) + 1][k]);  // 可根据题意改变操作符
    
25. }
    
26. 
    
27. int main() {
    
28.     cin >> n;
    
29.     for (int i = 1; i <= n; i++) {
    
30.         cin >> a[ i];
    
31.     }
    
32.     initST();  // 预处理 ST 表
    
33. 
    
34.     int q, l, r;
    
35.     cin >> q;
    
36.     while (q--) {
    
37.         cin >> l >> r;
    
38.         int zuida = queryST(l, r);
    
39.         int zuixiao = *min_element(a+l, a+r+1);
    
40.         cout << zuida - zuixiao << endl;
    
41.     }
    
42. 
    
43.     return 0;
    
44. }
    

复制代码

这段代码使用了 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 问题：

1. 
   
2. int main(){
   
3.     scanf("%d%d", &n, &q);
   
4.     for (int i = 1; i <= n; i++) {
   
5.         输入  ai
   
6.         f[0][i] = a[i];
   
7.     }
   
8.     for (int j = 1; j <= 20; ++j) {
   
9.                 for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
   
10.                         f[j][i] = max(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);
    
11.                 }
    
12.         }
    
13.     for (int i = 1; i <= q; i++) {
    
14.         读入 l,r
    
15.         if (l > r) swap(l, r);
    
16.         unsigned int x = __lg(r - l + 1);
    
17.         输出 max(f[x][l], f[x][r - (1 << x) + 1]);
    
18.     }
    
19. }

复制代码

也不需要倍增呃

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

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int maxn = 50010;
   
5. int n, h[maxn], q, l, r, log_2[maxn], rmax[maxn][18], rmin[maxn][18];
   
6. 
   
7. void init() {
   
8.     for (int i = 1; i <= n; i++) rmax[i][0] = rmin[i][0] = h[i];
   
9.     for (int j = 1; (1 << j) <= n; j++)
   
10.         for (int i = 1; i <= n - (1 << j) + 1; i++) {
    
11.             rmax[i][j] = max(rmax[i][j - 1], rmax[i + (1 << j - 1)][j - 1]);
    
12.             rmin[i][j] = min(rmin[i][j - 1], rmin[i + (1 << j - 1)][j - 1]);
    
13.         }
    
14. }
    
15. 
    
16. int mymax(int l, int r) {
    
17.     int x = log_2[r - l + 1];
    
18.     return max(rmax[l][x], rmax[r - (1 << x) + 1][x]);
    
19. }
    
20. 
    
21. int mymin(int l, int r) {
    
22.     int x = log_2[r - l + 1];
    
23.     return min(rmin[l][x], rmin[r - (1 << x) + 1][x]);
    
24. }
    
25. 
    
26. int main() {
    
27.     cin >> n >> q;
    
28.     for (int i = 1; i <= n; i++) cin >> h[i];
    
29.     for (int i = 2; i <= n; i++) log_2[i] = log_2[i >> 1] + 1;
    
30.     init();
    
31.     while (q--) {
    
32.         cin >> l >> r;
    
33.         cout << mymax(l, r) - mymin(l, r) << endl;
    
34.     }
    
35. 
    
36.     return 0;
    
37. }

复制代码

你不是过了吗？

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=" "哈哈