https://ac.nowcoder.com/acm/contest/11256/K

比赛时想到st表了，然后是尺取法，但是对尺取法理解不够深刻？还是脑子没转过来，尺取法写错了

观察后发现单调性

st表 模板

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 200010, M = 18;

int n, m;
int w[N];
int f[N][M];
//int fmin[N][M];

void init()
{
    for (int j = 0; j < M; j ++ )
        for (int i = 1; i + (1 << j) - 1 <= n; i ++ )
            if (!j)
            {
                f[i][j] = w[i];
                //fmin
            }
            else 
            {
                f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
                //fmin
            }
}

int query(int l, int r)
{
    int len = r - l + 1;
    int k = log(len) / log(2);

    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    init();

    scanf("%d", &m);
    while (m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", query(l, r));
    }

    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/205231/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这是比赛时超时的O(mn log n)

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;

int a[N];
int mx[N][30];//最大值 
int mn[N][30];//最小值 

//预处理 
void init(int n)
{
    for(int i=1;i<=n;i++){
        mx[i][0]=a[i];
        mn[i][0]=a[i];
    }

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

int search(int l,int r)//l和r范围为1~n 
{
    int k=log2(r-l+1);
    int t1=min(mn[l][k],mn[r-(1<<k)+1][k]);//区间最小值 
    int t2=max(mx[l][k],mx[r-(1<<k)+1][k]);//区间最大值 
    return t2-t1;
}
int check(int r,int k)
{
    int R=r;//R用来search 
    if(search(1,R)<k) return 0;
    r--;
    int l=1;
    int mid;
    while (l < r)
    {
        int mid = l + r+1 >> 1;
        if (search(mid,R) >= k) l = mid;
        else r = mid - 1;
    }
    return l;
}
int main()
{   int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    init(n);  int k;
    for(int i=1;i<=m;i++)
    {
        cin>>k;
        int cnt=0; 
        int l,r;
        int d;
        for(r=2;r<=n;r++)        //设定左右区间初始化为1
        {
            d=check(r,k+1);
            cnt+=d;
        }
        cout<<cnt<<endl;                    
    }
    return 0;
}

答案 O(nm)

他们都说是双指针，这与我在acwing上学到的双指针不同，倒是和我刷过的尺取法相识

#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; }

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;
}