ST表和区间最值
ST表和区间最值
ST表
ST表可以通过 O(nlogn) 的预处理然后在 O(1) 的时间内算出某段区间的最值，空间复杂度也为 O(nlogn)。原理是利用了倍增和动态规划的思想，设 dp[i][j] 表示从第 i 个数开始的 2^j 个数的最值，状态转移为：dp[i][j] = max(dp[i][j-1],dp[i + (2^{j-1})][j-1])，若求最小值则用 min ，即将长度为 2^j 的区间对半分为两个长度为 2^{j-1} 的两个小区间，分别求最值 。由于要用到log运算，介绍一种 log_2 的预处理方法：
lg[0] = -1;
for(int i = 1; i <= n; i++) lg[i] = lo[i>>1]+1;那么，可以写出ST表的预处理函数：
int a[maxn];//需要求最值的数组，以求最大值为例
void build(int n) {
for(int i = 1; i <= n; i++) dp[i][0] = a[i];//自己一个数时的最值就是自己
int lim = lg[n];//求出最大的lim使得 2 ^ lim <= n
for(int j = 1; j <= lim; j++)
for(int i = 1; i <= n - (1 << j) + 1; i++)
dp[i][j] = max(dp[i][j-1],dp[i + (1<<(j-1))][j-1]);
}如果我们要求某个区间 L 到 R 的最大值，我们先找到最大的 k 使得 2^k \le r-l+1 \le 2^{k+1} ，那么区间的最大值 mx = max(dp[l][k],dp[r – (1<<k) + 1][k])2^k 的最大值和 以 R 结束的长度为 2^k 的最大值中取最大值，由于是取最值，所以区间重叠没有影响，函数为：
int cal1(int l, int r) {
int k = lg[r - l + 1];
return max(dp2[l][k], dp2[r - (1 << k) + 1][k]);
}区间最值的一个性质
King of Range（2021牛客暑期多校训练营5 K题）
题意
给你1e5个数，求这些数组成的数列中，有多少对区间满足最大值和最小值的差小于 k。
分析
对于一个区间来说，如果将左边界向右移动，那么最大值只会不变或者变小，最小值只会不变或者变小；将右边界向右移动，最大值只会不变或者变大，最小值只会不变或者变小。所以，如果确定左边界 L 后，找到最小的右边界 R 满足题目要求，那么对于所有的以 L 为左端点和R右边任意一个点为右端点的区间都是满足题目要求的。于是我们可以从1开始枚举每个左端点，然后找到它最小的右端点，然后累加答案即可。由于左端点从左向右枚举，那么最大值只能变小，最小值只能变大，即使得情况更加不满足题目要求，倘若将右端点再向左移动，情况会更加不满足题目要求，所以右端点只可能向右移动不可能回头，故算法是 O(n) 的，但是当左端点向右移动后，不知道此刻的最小值和最大值为多少，可以用ST表预处理然后 O(1) 计算最值，故整体复杂度为 O(nlogn)。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
int a[maxn], dp1[maxn][50], dp2[maxn][50];
int mp[maxn];
int cal1(int l, int r) {
int k = mp[r - l + 1];
return max(dp2[l][k], dp2[r - (1 << k) + 1][k]);
}
int cal2(int l, int r) {
int k = mp[r - l + 1];
return min(dp1[l][k], dp1[r - (1 << k) + 1][k]);
}
int main(int argc, char const *argv[]) {
int n, m;
cin >> n >> m;
mp[0] = -1;
for(int i = 1; i <= n; i++) mp[i] = mp[i>>1]+1;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
int lim = mp[n];
for (int i = 1; i <= n; i++) dp1[i][0] = dp2[i][0] = a[i];
for (int j = 1; j <= lim; j++) {
for (int i = 1; i <= n - (1 << j) + 1; i++) {
dp1[i][j] = min(dp1[i][j - 1], dp1[i + (1 << (j - 1))][j - 1]);
dp2[i][j] = max(dp2[i][j - 1], dp2[i + (1 << (j - 1))][j - 1]);
}
}
while (m--) {
int k;
cin >> k;
int r = 1;
LL ans = 0;
for (int l = 1; l <= n; l++) {
int ma = cal1(l, r), mi = cal2(l, r);
while (r < n && ma - mi <= k) {
r++;
if (a[r] > ma) ma = a[r];
if (a[r] < mi) mi = a[r];
}
// printf("%d %d %d\n",l, r, cal(l,r));
if (ma - mi > k)
ans += (n - r + 1);
else
break;
}
printf("%lld\n", ans);
}
return 0;
}腾讯云开发者
