原题链接:https://www.luogu.com.cn/problem/P2880
题意解读:在若干个不定长区间里,求区间最大值与最小值之差
解题思路:
对于区间求最值,通常有几种方式:
1、暴力法,通过枚举所有的区间来计算区间最值
2、单调队列,针对区间长度固定的情况
3、ST表,针对区间长度不固定且元素不会发生改变的情况
4、树状数组,针对区间长度不固定且元素会发生改变的情况
这里显然是一个ST表的模版题。
首先,看看暴力法计算区间最值的过程,以最大值为例:
for(int i = 1; i <= n; i++)
{
int maxx = a[i];
for(int j = i + 1; j <= n; j++)
{
maxx = max(maxx, a[j]); //s[i][j]表示从a[i]~a[j]的最大值
s[i][j] = maxx;
}
}
要枚举以所有元素开始的所有可能长度区间,整个复杂度是O(n^2)的。
ST表基于这样的原理:
要计算区间[i, j]的最值,只需要计算[i, k]以及[k, j]的最值,其中[i,k]和[k,j]允许部分重叠
我们不需要预计算所有区间的最值,利用倍增的思想,我们只需要计算从每一个元素i开始,长度为2^j的区间的最值
设st[i][j]表示从i开始,长度是2^j的区间的最大值
根据定义可知:st[i][0] = a[i]
然后对st进行预处理:
for(int j = 1; j <= log2(n); j++) //枚举所有可能的区间长度2^j
{
for(int i = 1; i + (1 << j) - 1 <= n; i++) //枚举区间起点
{
//从i开始长度为2^j的区间最大值 = max(从i开始长度为2^j/2的区间最大值,从i+2^j/2开始长度为2^j/2的区间最大值)
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
对于给定区间[l,r],如何计算最大值呢?
首选确定一个区间长度2^len,使得l开始长度为2^len的区间与r结束长度为2^len的区间重叠,这样[l,r]的最大值就是max(st[l][len], st[r-(1<<len)+1][r])
len的计算方式:
int len = log2(r - l + 1);
100分代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 50005, M = 20; //M = log2(N) + 5
int n, q;
int a[N];
int st_max[N][M], st_min[N][M];
int main()
{
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++)
{
st_max[i][0] = st_min[i][0] = a[i];
}
for(int j = 1; j <= log2(n); j++)
{
for(int i = 1; i + (1 << j) - 1 <= n; i++)
{
st_max[i][j] = max(st_max[i][j - 1], st_max[i + (1 << (j - 1))][j - 1]);
st_min[i][j] = min(st_min[i][j - 1], st_min[i + (1 << (j - 1))][j - 1]);
}
}
int l, r;
while(q--)
{
cin >> l >> r;
int len = log2(r - l + 1);
int maxx = max(st_max[l][len], st_max[r - (1 << len) + 1][len]);
int minx = min(st_min[l][len], st_min[r - (1 << len) + 1][len]);
cout << maxx - minx << endl;
}
return 0;
}
标签:int,洛谷题,len,st,区间,P2880,Balanced,长度,最值 From: https://www.cnblogs.com/jcwy/p/18404792