hack数据的序列不是升序的。

提交记录

提交代码:

#include<bits/stdc++.h>
using namespace std;

struct qqq{
	int l,r;
	int num;
}b[1000005];
int len;

int n,q;
int a[1000005],px[1000005];

int ST_max[1000005][25];
int Log2[1000005];
int l,r;

void build_Log2(){
	Log2[0]=-1;
	for(int i=1;i<=len;++i){
		Log2[i]=Log2[i>>1]+1;
	}
	return;
}

void build_ST(){
	for(int i=1;i<=len;++i){
		ST_max[i][0]=b[i].r-b[i].l+1;
	}
	for(int lg=1;lg<=Log2[len];++lg){
		for(int i=1;i<=len;++i){
			ST_max[i][lg]=max(ST_max[i][lg-1],ST_max[i+(1<<(lg-1))][lg-1]);
		}
	}
	return;
}

int get_ST_max(int L,int R){
	if(L>R){
		return 0;
	}
	return max(ST_max[L][Log2[R-L+1]],ST_max[R-(1<<Log2[R-L+1])+1][Log2[R-L+1]]);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		if(i!=1 && a[i-1]>a[i]){
		    return 1;//RE 点
		}
	}
	for(int i=1;i<=n;++i){
		if(a[i]!=a[i-1] || i==1){
			++len;
			b[len].l=i;
		}
		px[i]=len;
		b[len].r=i;
	}
	build_Log2();
	build_ST();
	while(q--){
		cin>>l>>r;
		if(px[l]==px[r]){
			cout<<r-l+1<<'\n';
		}
		else{
		    cout<<max(max(b[px[l]+1].l-l,r-b[px[r]-1].r),get_ST_max(px[l]+1,px[r]-1))<<'\n';
		}
	}
	return 0;
}