完美子区间

给定序列 \(a1,a2,⋯,an\) ，求一个最长的子区间 \(al,al+1,⋯,ar\) ，满足

\(A ≤ \max(al, al+1, al+2, ..., ar) − \min(al, al+1, al+2, ..., ar) ≤ B\)

我们可以这样子考虑， 如果没有A的限制， 怎么做？

明显可以发现 \max(al, al+1, al+2, ..., ar) − \min(al, al+1, al+2, ..., ar) 是单调递增的

所以越大， 条件越难满足

可以枚举左端点，二分出右端点

然而我们求出的是， 满足条件的最大的r, 所以可以轻易算出满不满足A的条件

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
 
const int N= 1e6+ 5;
 
int a[N];
int infa[N][20], axfa[N][20], Two[N]; 
int n, A, B; 
 
int read()
{
    int x= 0, f= 0; char c= getchar();
    while(!isdigit(c)) f|= c== '-', c= getchar();
    while(isdigit(c)) x= (x<< 1)+ (x<< 3)+ c- '0', c= getchar();
    return f? -x : x;
}
 
int query(int l, int r)
{
    int u= Two[r- l+ 1];
    return max(axfa[l][u], axfa[r- (1<< u)+ 1][u])- min(infa[l][u], infa[r- (1<< u)+ 1][u]);
}
 
int main()
{
    cin>> n>> A>> B;
    for(int i= 1; i<= n; i++ ) a[i]= read();
    for(int i= 1; i<= n; i++ ) infa[i][0]= axfa[i][0]= a[i];
    for(int i= 2; i<= n; i++ ) Two[i]= Two[i>> 1]+ 1;
    for(int j= 1; j<= Two[n]; j++ )
        for(int i= 1; i+ (1<< j)- 1<= n; i++ ) infa[i][j]= min(infa[i][j- 1], infa[i+ (1<< j- 1)][j- 1]), axfa[i][j]= max(axfa[i][j- 1], axfa[i+ (1<< j- 1)][j- 1]);
    int ans= 0;
    for(int i= 1; i<= n; i++ )
    {
        int l= i, r= n;
        while(l< r)
        {
            int mid= (l+ r+ 1)>> 1;
            if(query(i, mid)<= B) l= mid;
            else r= mid- 1;
        }
        if(query(i, l)>= A) ans= max(ans, l- i+ 1);
    }
    cout<< ans<< endl;
     
    return 0;
}

然而这个时间复杂度不靠谱 我们想想换方法

我们可以枚举右端点， 会发现 如果对于前面的r, 这个l不满足了, 那后面的r也不会满足

我们可以开两个单调队列， 具体见代码

#include <bits/stdc++.h>
using namespace std;
 
const int N= 1e6+ 5;
 
int a[N];
int q1[N], h1, t1= -1, q2[N], h2, t2= -1; 
 
int main()
{
    int n, A, B; cin>> n>> A>> B;
    for(int i= 0; i< n; i++ ) scanf("%d", &a[i]);
    int maxn= 0; int m1= -1, m2= -1;
    for(int i= 0; i< n; i++ )
    {
        while(h1<= t1&& a[i]> a[q1[t1]]) t1-- ;     //维护上升的单调队列
        q1[++ t1]= i;
        while(h2<= t2&& a[i]< a[q2[t2]]) t2-- ;     //维护下降的
        q2[++ t2]= i;
        while(h1<= t1&& h2<= t2&& a[q1[h1]]- a[q2[h2]]> B)
        {
            if(q1[h1]< q2[h2]) m1= q1[h1], h1++ ;          //满足不了就跳过， 选择下标小的
            else m2= q2[h2], h2++ ;
        }
        if(a[q1[h1]]- a[q2[h2]]>= A&& a[q1[h1]]- a[q2[h2]]<= B) maxn= max(maxn, i- max(m1, m2));
    }
    cout<< maxn<< endl;
     
    return 0;
}