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])$ ，即从 L 开始长度为 $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;
}