網(wǎng)站建設免費軟件有哪些推特最新消息今天
【題目鏈接】
ybt 1541:【例 1】數(shù)列區(qū)間最大值
【題目考點】
1. RMQ問題
RMQ問題是給定一個序列,多次求區(qū)間最值的問題。
常用解法:
- ST表:離線算法,預處理 O ( n log ? n ) O(n\log n) O(nlogn),區(qū)間查詢 O ( 1 ) O(1) O(1)
- 線段樹:在線算法,預處理 O ( n ) O(n) O(n),區(qū)間查詢 O ( log ? n ) O(\log n) O(logn)
【解題思路】
解法1:ST表
概念及解析見洛谷 P3865 【模板】ST 表 && RMQ 問題
解法2:線段樹
基本概念及解析見洛谷 P3374 【模板】樹狀數(shù)組 1(線段樹解法)
線段樹中每個結點保存的值為該結點表示的區(qū)間中的最大值。
使用孩子結點的值更新雙親結點的值時(pushUp操作),取左右孩子結點的值的最大值,即為當前結點的值。
區(qū)間查詢時:
- 如果當前結點表示的區(qū)間被待查詢區(qū)間完全包含,則返回當前結點的值。
- 如果當前結點表示的區(qū)間沒有被待查詢區(qū)間包含,則求出左右孩子結點表示的區(qū)間在待查詢區(qū)間中的最大值,返回這兩個值的最大值。
【題解代碼】
解法1:ST表
#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define L 30
int a[N], lg[N], f[N][L];//f[i][j]:a[i]~a[i+2^j-1]中的最大值
void initLg(int n)
{for(int i = 2; i <= n; ++i)lg[i] = lg[i/2]+1;
}
int query(int l, int r)
{int k = lg[r-l+1];return max(f[l][k], f[r-(1<<k)+1][k]);
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, l, r;cin >> n >> m;initLg(n);for(int i = 1; i <= n; ++i)cin >> a[i];for(int i = 1; i <= n; ++i)f[i][0] = a[i];for(int j = 1; j <= lg[n]; ++j)for(int i = 1; i+(1<<j)-1 <= n; ++i)f[i][j] = max(f[i][j-1], f[i+(1<<(j-1))][j-1]);while(m--){cin >> l >> r;cout << query(l, r) << '\n';}return 0;
}
解法2:線段樹
#include<bits/stdc++.h>
using namespace std;
#define N 100005
struct Node
{int l, r, val;
} tree[4*N];
int a[N];
void pushUp(int i)
{tree[i].val = max(tree[2*i].val, tree[2*i+1].val);
}
void build(int i, int l, int r)
{tree[i].l = l, tree[i].r = r;if(l == r){tree[i].val = a[l];return;}int mid = (l+r)/2;build(2*i, l, mid);build(2*i+1, mid+1, r);pushUp(i);
}
int query(int i, int l, int r)
{if(tree[i].l > r || tree[i].r < l)return INT_MIN;if(l <= tree[i].l && tree[i].r <= r)return tree[i].val;return max(query(2*i, l, r), query(2*i+1, l, r));
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, l, r;cin >> n >> m;for(int i = 1; i <= n; ++i)cin >> a[i];build(1, 1, n);while(m--){cin >> l >> r;cout << query(1, l, r) << '\n';}return 0;
}