#C231116A. 玩具序列(sequence)

标签（Label）

• 单调栈

网址（Website）

$\qquad$ 题目详情 - 玩具序列(sequence) - Super

$\qquad$ 题解 - 玩具序列(sequence) - Super

题解（Solution）

$\qquad$题解也很简单，直接走一个单调队列，求出对于当前的 $a_i$ 最多能像左右延伸多少就好啦，但其实只需要考虑做从左到右的，因为如果当前的 $a_i$ 可以延伸到一个位置，那么 $a_{i+1}$ 同样在满足条件的情况下也可以，那么一定能得到以当前位置为结尾的想左延伸的最大区间，所以只用跑一遍。

$\qquad$我当时还以为需要同时求出对于当前点满足条件的左边和右边，结果挂了 $70pts$ 。`(*>﹏<*)′

代码（Code）

#include<bits/stdc++.h>
#include<deque>
#define For(i,l,r) for(int i=l;i<=r;i++) 
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
inline int input(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}
deque<pair<int,int>> qmax,qmin;
const int N = 3012345;
int n,k,ans,lst=1,a[N];

signed main(){
	string str("sequence");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	k=input(),n=input();For(i,1,n) a[i]=input();
	For(i,1,n){
		while(qmax.size() && qmax.back().first<a[i]) qmax.pop_back();
		while(qmin.size() && qmin.back().first>a[i]) qmin.pop_back();
		while(qmax.size() && abs(qmax.front().first-a[i])>k) lst=qmax.front().second+1,qmax.pop_front();
		while(qmin.size() && abs(qmin.front().first-a[i])>k) lst=qmin.front().second+1,qmin.pop_front();
		qmax.push_back({a[i],i});
		qmin.push_back({a[i],i});
		ans=max(ans,i-lst+1); 
	}return printf("%d",ans),0;
}