引入：
ST算法（Sparse Table），以求最大值为例，设表示这个区间内的最大值，那么在询问到区间的最大值时答案就是其中是满足(即长度)的最大的即。

具体关于的推导，看这个文章，Pecco

动态规划预处理

for (int i = 1; i <= 21; ++i)
        for (int j = 1; j + (1 << i) - 1 <= n; ++j)
        {
            Min[j][i] = min(Min[j][i - 1], Min[j + (1 << (i - 1))][i - 1]);
            Max[j][i] = max(Max[j][i - 1], Max[j + (1 << (i - 1))][i - 1]);
        }

的预处理：

for (int i = 2; i <= n; ++i)
        Log2[i] = Log2[i / 2] + 1;

预处理函数：

void init(){
    for (int i = 2; i <= n; ++i)
        Log2[i] = Log2[i / 2] + 1;
    for (int i = 1; i <= 21; ++i)
        for (int j = 1; j + (1 << i) - 1 <= n; ++j)
        {
            Min[j][i] = min(Min[j][i - 1], Min[j + (1 << (i - 1))][i - 1]);
            Max[j][i] = max(Max[j][i - 1], Max[j + (1 << (i - 1))][i - 1]);
        }
}

区间查询最大值，最小值

int find(int l,int r){

        int s = Log2[r - l + 1];
        int ma = max(Max[l][s], Max[r - (1 << s) + 1][s]);
        //int mi = min(Min[l][s], Min[r - (1 << s) + 1][s]);
        return ma;
        //return mi;
}

完整：

int Log2[MAXN], Min[MAXN][21], Max[MAXN][21];
void init(){
    for (int i = 2; i <= n; ++i)
        Log2[i] = Log2[i / 2] + 1;
    for (int i = 1; i <= 21; ++i)
        for (int j = 1; j + (1 << i) - 1 <= n; ++j)
        {
            Min[j][i] = min(Min[j][i - 1], Min[j + (1 << (i - 1))][i - 1]);
            Max[j][i] = max(Max[j][i - 1], Max[j + (1 << (i - 1))][i - 1]);
        }
}
int find(int l,int r){

        int s = Log2[r - l + 1];
        int ma = max(Max[l][s], Max[r - (1 << s) + 1][s]);//最大
        //int mi = min(Min[l][s], Min[r - (1 << s) + 1][s]);//最小
        return ma;
        //return mi;
}

输入：

for (int i = 1; i <= n; ++i)
    {
        int x = read();
        Min[i][0] = x;
        Max[i][0] = x;
    }

King of Range

给你一个序列a1~an,m组查询，每一组查询问有多少对,到最大值减最小值大于K。

RMQ+双指针

代码：

#include <bits/stdc++.h>
#define MAXN 200000
#define bug(x) cerr<<#x<<" : "<<x<<endl;
typedef long long ll;
using namespace std;
int read()
{
    int ans = 0;
    char c = getchar();
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
    {
        ans = ans * 10 + c - '0';
        c = getchar();
    }
    return ans;
}
int Log2[MAXN], Min[MAXN][21], Max[MAXN][21];

bool chk(int l,int r,int k){

        int s = Log2[r - l + 1];
        int ma = max(Max[l][s], Max[r - (1 << s) + 1][s]);
        int mi = min(Min[l][s], Min[r - (1 << s) + 1][s]);
        if(ma-mi>k) return true;
        return false;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("test.txt", "w", stdout);
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i)
    {
        int x = read();
        Min[i][0] = x;
        Max[i][0] = x;
    }
    for (int i = 2; i <= n; ++i)
        Log2[i] = Log2[i / 2] + 1;
    for (int i = 1; i <= 21; ++i)
        for (int j = 1; j + (1 << i) - 1 <= n; ++j)
        {
            Min[j][i] = min(Min[j][i - 1], Min[j + (1 << (i - 1))][i - 1]);
            Max[j][i] = max(Max[j][i - 1], Max[j + (1 << (i - 1))][i - 1]);
        }
    while(m--){
        int k=read();
        ll ans=0;
        for(int i=1,j=1;i<=n;i++){
            while(!chk(i,j,k)&&j<=n&&i<=j){
                j++;
            }

            if(j<=n) ans=ans+n-j+1;
        }
        cout<<ans<<endl;
    }
    return 0;
}