这篇文章上次修改于 378 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

本文共 2026 个字，阅读时长 ≈ 6 分钟

1826. 平衡子段

题目链接

题目描述

一个序列含有 N 个整数 $A_i$。现在给出两个整数 M、C，让你从原序列中寻找长度为 M，波动幅度不超过 C 的平衡子段。

所谓“长度为 M，波动幅度不超过 C 的平衡子段 ”，是指：

1. 在原序列中是连续的M个数
2. 记这M个数中的最大值为 Max，最小值为 Min，则 $Max-Min\leq C$

思路

固定长度的区间，让你找区间中的最大最小值，一眼RMQ问题，看看数据范围，可以 $O(N\log N)$，直接莽一发ST表

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x*f;
}
const int N=1000006,M=22;
int n,m,c;
int fd[N][M],fx[N][M];
//ST表查询
inline int da(int l,int r){
    int x=(int)log2(r-l+1);
    return max(fd[l][x],fd[r-(1<<x)+1][x]);
}
inline int xiao(int l,int r){
    int x=(int)log2(r-l+1);
    return min(fx[l][x],fx[r-(1<<x)+1][x]);
}
int main()
{
    n=read();
    m=read();
    c=read();
    for(int i=1;i<=n;++i){
        fd[i][0]=read();
        fx[i][0]=fd[i][0];
    }
    //预处理ST表
    for(int j=1;j<M;++j)
        for(int i=1;i+(1<<j)-1<=n;i++){
            fx[i][j]=min(fx[i][j-1],fx[i+(1<<(j-1))][j-1]);
            fd[i][j]=max(fd[i][j-1],fd[i+(1<<(j-1))][j-1]);
        }
    vector<int> a;
    //枚举起点判断合法性
    for(int i=1;i+m-1<=n;++i){
        if(da(i,i+m-1)-xiao(i,i+m-1)<=c) a.push_back(i);
    }
    if(a.empty()) printf("NONE\n");
    else{
        for(int i:a) printf("%d\n",i);
    }
    return 0;
}

据说可以 $O(N)$，既然是一个个区间从1到n枚举过去，考虑用单调队列维护区间最大最小值。以最大值举例，每次加一个数x的时候从队尾弹出比x小的，然后从队头弹出距离大于m的，最后取出最大最小值判断即可。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x*f;
}
const int N=10000007;
int n,m,c,h,t,hh,tt;
int a[N];
typedef pair<int,int> pii;
pii da[N],xiao[N];
vector<int> ans;
int main()
{
    n=read();
    m=read();
    c=read();
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=1;i<=n;++i){
        //最大值单调队列
        //先弹小的
        while(h<t&&da[t].second<a[i]) --t;
        //再弹远的
        while(h<t&&da[h+1].first+m-1<i) ++h;
        //最小值
        while(hh<tt&&xiao[tt].second>a[i]) --tt;
        while(hh<tt&&xiao[hh+1].first+m-1<i) ++hh;
        //别忘记入队
        da[++t]={i,a[i]}; xiao[++tt]={i,a[i]};
        if(i>=m){
            if(da[h+1].second-xiao[hh+1].second<=c) ans.push_back(i-m+1);
        }
    }
    if(ans.empty()) printf("NONE\n");
    else for(int i:ans) printf("%d\n",i);
    return 0;
}