求条(悬棺)
查看原帖
求条(悬棺)
916086
yaoshuen楼主2025/1/23 15:27
#include <bits/stdc++.h>
using namespace std;
inline int read(){
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*f;
}
const int N=1e5+20;
const int inf=1e8+1e8+1e8+1e8+1e8*6;
int n,q;
int a[N];
int st[N][30];
void init(){
	
	for(int i=1;i<=n;i++) st[i][0]=a[i];
	a[0]=inf;
	a[n+1]=inf;
	st[0][0]=inf;
	st[n+1][0]=inf;
	n++;
	for(int i=1;i<=29;i++){
		for(int j=1;j<=n&&(j+(1<<(i-1)))<=n;j++){
			st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
		}
	}
}
int getmax(int L,int R){
	int k=log2(R-L+1);
	return max(st[L][k],st[R-(1<<k)+1][k]);
}
int Lcheck(int x,int y){ //x>y 
	int m=getmax(y,x-1);
	int l=x+1,r=n,mid=0;
	int pos=0;
	while(l<=r){
		mid=(l+r)>>1;
		if(getmax(x+1,mid)<m){
			pos=mid;
			l=mid+1;
		}else r=mid-1;
	}
	if(pos==0) return x-y+1;
	return pos-x+1+x-y;
}
int Rcheck(int x,int y){ //x<y 
	int m=getmax(x+1,y);
	int l=0,r=x-1,mid=0;
	int pos=0;
	while(l<=r){
		mid=(l+r)>>1;
		if(getmax(mid,x-1)<m){
			pos=mid;
			r=mid-1;
		}else l=mid+1;
	}
	if(pos==0) return y-x+1;
	return x-pos+1+y-x;
}
int query(int p,int k){
	if(k==1) return 1;
	int pos=0,pos2=0,t1=0;
	int l,r,mid;
	if(p-k>=0){
		
		l=p-k,r=p-1,mid=0;

		while(l<=r){
			mid=(l+r)>>1;
			if(Rcheck(mid,p)>k){
				l=mid+1;
				pos=mid;
			}else r=mid-1;
		}
		l=p-k+1,r=p-1;
		while(l<=r){
			mid=(l+r)>>1;
			if(Rcheck(mid,p)>=k){
				l=mid+1;
				pos2=mid;
			}else r=mid-1;
		}
	}
	//printf("111\n");
	t1=max(0,pos2-pos);
	//printf("!!!%d\n",t1);
	l=p+1,r=p+k,mid=0;
	pos=pos2=0;
	if(p+k<=n){
		while(l<=r){
			mid=(r+l)>>1;
			if(Lcheck(mid,p)>k){
				r=mid-1;
				pos=mid;
			}else l=mid+1;
		}
		l=p+1,r=p+k-1;
		while(l<=r){
			mid=(l+r)>>1;
			if(Lcheck(mid,p)>=k){
				r=mid-1;
				pos2=mid;
			}else l=mid+1;
		}
	}
	//printf("!!!%d %d\n",pos,pos2);
	return max(0,pos-pos2)+t1;
}
int main(){
	n=read();
	q=read();
	for(int i=1;i<=n;i++) a[i]=read();
	init();
	while(q--){
		int x=read();
		int y=read();
		printf("%d\n",query(x,y)); 
	}
	return 0;
}

2025/1/23 15:27
加载中...