求助90
查看原帖
求助90
235901
Always_Remember_It楼主2023/9/17 11:50
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int n,h[N],nxt[N];
int num,in[N],l[N],r[N],s[N],t[N];
void block(){
	num=sqrt(n);
	if(num*num!=n) ++num;
	int lar=num;
	if(num*(num-1)>=n&&num*num!=n) --lar;
	for(int i=1;i<num;i++){
		l[i]=r[i-1]+1;
		r[i]=i*lar;
	}
	l[num]=r[num-1]+1;
	r[num]=n;
	for(int i=1;i<=r[num-1];i++){
		in[i]=(i-1)/lar+1;
	}
	for(int i=l[num];i<=n;i++){
		in[i]=num;
	}
	for(int i=1;i<=num;i++){
		for(int j=l[i];j<=r[i];j++){
			if(h[j]>s[i]){
				s[i]=h[j];
				t[i]=j;
			}
		}
	}
}
int ask(int lt,int rt){
	int res=0,pt=0;
	if(in[lt]==in[rt]){
		for(int i=lt;i<=rt;i++){
			if(h[i]>res){
				res=h[i];
				pt=i;
			}
		}
		return pt;
	}
	for(int i=lt;i<=r[in[lt]];i++){
  		if(h[i]>res){
  			res=h[i];
  			pt=i;
		}
	}
	for(int i=in[lt]+1;i<in[rt];i++){
  		if(s[i]>res){
  			res=s[i];
  			pt=t[i];
		}
	}
	for(int i=l[in[rt]];i<=rt;i++){
  		if(h[i]>res){
  			res=h[i];
  			pt=i;
		}
	}
	return pt;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>h[i];
	}
	block();
	for(int i=n;i>=1;i--){
		nxt[i]=max(nxt[i+1],h[i]);
	}
	int l1=1,r1=2,maxn=0;
	while(r1<=n){
		if(l1==r1){
			++r1;
			continue;
		}
		if(h[r1]<=h[l1]){
			if(r1-l1<=1){
				++l1;
				++r1;
				continue;
			}
			int now=0,ps=ask(l1,r1);
			maxn=max(maxn,ps-l1+1);
			++l1;
			continue;
		}
		if(h[r1]==nxt[l1]){
			maxn=max(maxn,r1-l1+1);
			l1=r1+1;
			r1+=2;
			continue;
		}
		++r1;
	}
	maxn=max(maxn,n-l1+1);
	if(maxn==1) cout<<0<<endl;
	else cout<<maxn<<endl;
	return 0;
}
2023/9/17 11:50
加载中...