109徐守佳

用户名：dotcpp0787174

访问量：999

签　名：

想AC的我戴上了WA面具

等　　级
排　　名	919
经　　验	3474
参赛次数	1
文章发表	30
年　　龄	20
在职情况	学生
学　　校	内江师范学院
专　　业	虹夏虹夏虹

　　自我简介：

TA的其他文章

[信息学奥赛一本通T1550-花神游历各国] 区间更新负优化
浏览：16

[蓝桥杯2022年第十三届决赛真题-最大数字] 贪心+dfs
浏览：57

题可以贪心做，人要看准了爱.
浏览：54

你可能喜欢

[信息学奥赛一本通T1545-Balanced Lineup] RMQ

　　作者: 109徐守佳　　　　发表时间：2024-10-22 23:23:31 浏览：21　|　评论：0　

原题链接：信息学奥赛一本通T1545-Balanced Lineup

## 解题思路
1. **分析问题**：他让我们找出一个区间里的最大最小值然后相减,中途没有修改操作,可以用两个ST表维护一个最大值,最小值,查询时相减就行.
2. **确定算法**：ST表

## 代码实现
```cpp
#include<bits/stdc++.h>
#define ULL unsigned long long
#define int long long
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define all(v) v.begin(), v.end()
#define PII pair<int,int>
using namespace std;
constexpr int N =  1 *1e6 + 10,M = 5 * 1e4 + 10,inf = 0x3f3f3f3f;

const int MAXN = 20;

int n,q;
int w[N];
int maxf[M][MAXN],minf[M][MAXN];
void init()
{
    for(int j=0;j<MAXN;j++)
    {
        for(int i=1;i + (1 << j) - 1 <= n ; i++)
        {
            if(!j) minf[i][j] = maxf[i][j] = w[i];
            else
            {
                minf[i][j] = min(minf[i][j-1],minf[i + (1<<(j-1))][j-1]),
                maxf[i][j] = max(maxf[i][j-1],maxf[i + (1<<(j-1))][j-1]);
            }
        }
    }
}
int query(int l,int r)
{
    int len = r - l + 1;
    int k = log(len)/log(2);
    return max(maxf[l][k],maxf[r - (1<<k) + 1][k]) - min(minf[l][k],minf[r - (1<<k) + 1][k]);
}
void solve()
{
    cin >> n >> q;
    for(int i=1;i<=n;i++) cin >> w[i];
    init();
    while (q--)
    {
        int l,r;
        cin>>l>>r;
        cout<<query(l,r)<<endl;
    }
    
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(nullptr),cout.tie(nullptr);
    int _=1;
    // cin>>_;
    while(_--)
    {
        solve();
    }
    return 0;
}

/**
 *    author: Nijika_jia
 *    created: 2024.10.22 22:43:14
 */
```
## 复杂度分析
**时间复杂度：**
初始化：O(n * log(n))
查询：O(1) 每次查询
总时间复杂度：O(n * log(n) + q)，其中 q 是查询的次数。

**空间复杂度：**
O(M * MAXN)，即 O(5 * 10^4 * 20)，约为 10^6

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

109徐守佳

TA的其他文章

你可能喜欢

回文数字（C++代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C二级辅导-求偶数和（C语言代码）

C语言训练-数字母（C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

[信息学奥赛一本通T1545-Balanced Lineup] RMQ

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）for循环

九宫重排（C++代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-温度转换（C语言代码）

大神老白（C语言代码）

班级人数（C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题12.3 （C++代码）

109徐守佳

TA的其他文章

你可能喜欢

回文数字 （C++代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C二级辅导-求偶数和 （C语言代码）

C语言训练-数字母 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

[信息学奥赛一本通T1545-Balanced Lineup] RMQ

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）for循环

九宫重排 （C++代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-温度转换 （C语言代码）

大神老白 （C语言代码）

班级人数 （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

WU-C语言程序设计教程（第三版）课后习题12.3 （C++代码）

回文数字（C++代码）

C二级辅导-求偶数和（C语言代码）

C语言训练-数字母（C语言代码）

　　评论区

九宫重排（C++代码）

C二级辅导-温度转换（C语言代码）

大神老白（C语言代码）

班级人数（C语言代码）