C20220725T2 运动

给定序列 \(s\) ,求满足 \(max\{s_{i,j}\}-min\{s_{i,j}\}\leq k\) 的最大长度 \(j-i\) 。 \(n\leq 3\times10^6\) 。（时限3s）

没想到 \(O(n\,log\,n)\) 没有被卡掉。首先判断区间的最大最小值可以用单调队列 \(O(n)\) 求出，然后就二分就好了，跑的飞快。

然后是 \(O(n)\) 的正解，其实只需要将思路转换一下，在单调队列中记录最大值和最小值，若 \(max-min>k\) 就 \(pop\) 出队，这样就是 \(O(n)\) 的了。（只有 \(O(n\,log\,n)\) 的代码）。

#include<bits/stdc++.h>
using namespace std;
struct IO{
    inline char read(){
        static const int IN_LEN=1<<18|1;
        static char buf[IN_LEN],*s,*t;
        return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
    }
    template <typename _Tp> inline IO & operator >> (_Tp&x){
        static char c11,boo;
        for(c11=read(),boo=0;!isdigit(c11);c11=read()){
            if(c11==-1)return *this;
            boo|=c11=='-';
        }
        for(x=0;isdigit(c11);c11=read())x=x*10+(c11^'0');
        boo&&(x=-x);
        return *this;
    }
    inline void push(const char &c) {
    	putchar(c);
	}
	template <class T>
	inline void write(T x){
		if (x < 0) x = -x, push('-');
		static T sta[35];
		T top = 0;
		do {
			sta[top++] = x % 10, x /= 10;
		} while (x);
		while (top) push(sta[--top] + '0');
	}
	template <class T>
	inline void write(T x, char lastChar){
		write(x),push(lastChar);
	}
}io;

int k,n;
int a[3000005];
int maxn[3000005],minn[3000005];

bool solve(int L){
	int l1=1,l2=1,r1=0,r2=0;
	for(int i=1;i<=n;++i){
		while(l1<=r1 && i-maxn[l1]>=L)
			++l1;
		while(l1<=r1 && a[maxn[r1]]<a[i])
			--r1;
		maxn[++r1]=i;
		while(l2<=r2 && i-minn[l2]>=L)
			++l2;
		while(l2<=r2 && a[minn[r2]]>a[i])
			--r2;
		minn[++r2]=i;
		if(i>=L){
			if(a[maxn[l1]]-a[minn[l2]]<=k)
				return 1;
		}
	}
	return 0;
}


int main(){
	io>>k>>n;
	for(int i=1;i<=n;++i)
		io>>a[i];
	int l=1,r=n+1;
	while(l<r){
		int mid=(l+r)>>1;
		int g=solve(mid);
		if(g)
			l=mid+1;
		else
			r=mid;
	}
	printf("%d",l-1);
	return 0;
}