网站做的支付宝接口,设计网站大全软件,免费cms建站五指,新上市手机【题目链接】
ybt 1541#xff1a;【例 1】数列区间最大值
【题目考点】
1. RMQ问题
RMQ问题是给定一个序列#xff0c;多次求区间最值的问题。 常用解法#xff1a;
ST表#xff1a;离线算法#xff0c;预处理 O ( n log n ) O(n\log n) O(nlogn)#xff0c;区间…【题目链接】
ybt 1541【例 1】数列区间最大值
【题目考点】
1. RMQ问题
RMQ问题是给定一个序列多次求区间最值的问题。 常用解法
ST表离线算法预处理 O ( n log n ) O(n\log n) O(nlogn)区间查询 O ( 1 ) O(1) O(1)线段树在线算法预处理 O ( n ) O(n) O(n)区间查询 O ( log n ) O(\log n) O(logn)
【解题思路】
解法1ST表
概念及解析见洛谷 P3865 【模板】ST 表 RMQ 问题
解法2线段树
基本概念及解析见洛谷 P3374 【模板】树状数组 1线段树解法 线段树中每个结点保存的值为该结点表示的区间中的最大值。 使用孩子结点的值更新双亲结点的值时pushUp操作取左右孩子结点的值的最大值即为当前结点的值。 区间查询时
如果当前结点表示的区间被待查询区间完全包含则返回当前结点的值。如果当前结点表示的区间没有被待查询区间包含则求出左右孩子结点表示的区间在待查询区间中的最大值返回这两个值的最大值。
【题解代码】
解法1ST表
#includebits/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[i2^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-l1];return max(f[l][k], f[r-(1k)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(1j)-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线段树
#includebits/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*i1].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 (lr)/2;build(2*i, l, mid);build(2*i1, mid1, 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*i1, 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;
}
