109徐守佳

用户名：dotcpp0787174

访问量：999

签　名：

想AC的我戴上了WA面具

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

　　自我简介：

TA的其他文章

[信息学奥赛一本通T1541-数列区间最大值] ST表
浏览：21

[信息学奥赛一本通T1545-Balanced Lineup] RMQ
浏览：21

[信息学奥赛一本通T1547-区间和]-分块写法
浏览：15

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言训练-最大数问题（C语言代码）.........关于-1

[信息学奥赛一本通T1541-数列区间最大值] ST表

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

原题链接：信息学奥赛一本通T1541-数列区间最大值

# 线段树常数大了得加点小细节才能过(~~反正我没过~~),静态询问嘛,就用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 *1e5 + 10,M = 5 * 1e3 + 10,inf = 0x3f3f3f3f;

int n,m;
int w[N];
int f[2*N][21];
void init()
{
    for(int j=0;j<21;j++)
    {
        for(int i = 1; i + (1 << j) - 1 <= n;  i++)
        {
            if(!j) f[i][j] = w[i];
            else f[i][j] = max(f[i][j-1],f[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(f[l][k],f[r-(1<<k)+ 1][k]);
}
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>w[i];
    init();
    while (m--)
    {
        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 00:07:19
 */
```

0.0分

1 人评分

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

109徐守佳

TA的其他文章

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

IP判断（C++代码）

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

C语言训练-最大数问题（C语言代码）.........关于-1

C二级辅导-计负均正（C语言代码）

[信息学奥赛一本通T1541-数列区间最大值] ST表

评论区

精彩推荐

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

C语言考试练习题_排列（C语言代码）

妹子杀手的故事（C语言代码）

C二级辅导-阶乘数列（C语言代码）

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

核桃的数量（C语言代码）

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

蚂蚁感冒（C语言代码）

C二级辅导-等差数列（C语言代码）

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

109徐守佳

TA的其他文章

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

IP判断 （C++代码）

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

C语言训练-最大数问题 （C语言代码）.........关于-1

C二级辅导-计负均正 （C语言代码）

[信息学奥赛一本通T1541-数列区间最大值] ST表

评论区

精彩推荐

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

C语言考试练习题_排列 （C语言代码）

妹子杀手的故事 （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

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

核桃的数量 （C语言代码）

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

蚂蚁感冒 （C语言代码）

C二级辅导-等差数列 （C语言代码）

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

IP判断（C++代码）

C语言训练-最大数问题（C语言代码）.........关于-1

C二级辅导-计负均正（C语言代码）

　　评论区

C语言考试练习题_排列（C语言代码）

妹子杀手的故事（C语言代码）

C二级辅导-阶乘数列（C语言代码）

核桃的数量（C语言代码）

蚂蚁感冒（C语言代码）

C二级辅导-等差数列（C语言代码）