K King of Range

1.方法：st表加双指针

2.题意

给你一个长为n的数组，有m次询问，每次询问给你一个k，问有多少对(l,r),使数组区间l到r的最大值与最小值的差大于k

3.思路

若给你个子数组发现最大值与最小值的差已经满足条件，那么是不是意味着在这个子数组的基础上在添加其他的元素，其最大值与最小值的差也会成立。所以我们可以用双子针，固定i的位置，来找最小的j。要在一个区间内找最小值，我们可以用st表。

4.代码如下

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }   
ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }

const int mod=1e9+7;
const int N=1e5+7;

int n,m,l,r;
int Log[N]; // 用来求log的
int stmax[N][22];
int stmin[N][22];

void fun(){//求log的函数
    Log[1]=0;
    for(int i=2;i<=n;i++)
        Log[i]=Log[i/2]+1;
}

bool search(int l,int r,ll k){//判断区间l到r是否可以
     int s=Log[r-l+1]; //求log的值
     int ma=max(stmax[l][s], stmax[r-(1<<s)+1][s]);//区间最大值
     int mi=min(stmin[l][s], stmin[r-(1<<s)+1][s]);//区间最小值
     if(ma-mi>k) return true; //判断是否大于k
     else return false;
}

int main(){
    while(cin>>n>>m){
        fun();
        for(int i=1;i<=n;i++) {cin>>stmax[i][0];stmin[i][0]=stmax[i][0];}
        for(int j=1;j<=21;j++)//构造st表
            for(int i=1;i+(1<<j)-1<=n;i++){
                stmax[i][j]=max(stmax[i][j-1],stmax[i+(1<<(j-1))][j-1]);
                stmin[i][j]=min(stmin[i][j-1],stmin[i+(1<<(j-1))][j-1]);
            }

        while(m--){
            ll k,ans=0;
            cin>>k;
            for(int i=1,j=1;i<=n;i++){
                while(!search(i,j,k)&&j<=n&&i<=j){//固定i的值，找到成立的j的最小值
                    j++;
                }
                if(j<=n) ans=ans+n-j+1; //如果某一子段可以，则无论后面加上什么数形成的数组都可以
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}