题目大意:现在有n个房子,从1到n从左向右排列。每个房子有一个高度,一个人要向通过这个房子,他的高度必须和房子的高度完全相等。你可以修改一个人的身高,给定你一个D,你能使一个人的身高最多增加D或最多减少D。

现在给定你次询问。询问类型1,将一个指定房子的高度修改成其他值。询问类型2,若一个人从一个房子出发,你的修改身高能力的上限为D(每通过一个房子可以修改一次),那么这个人在最远在哪个房子停下来?

房子的高度没什么用,真正有用的是相邻房子的高度差值。因此我们可以搞个绝对值差分数组存储相邻房子的高度差。然后我们可以直接暴力。而这里暴力会超时。我们可以观察,如果此人在第i个房子开始,到第j个房子停下。那么i到j之间各个相邻房子的高度差的绝对值小于等于D,换句话说,就是差分数组里i+1到j的最大值小于等于D。这个特性和线段树相似,所以我们对差分数组建立线段树。然后结合二分法找到此人停下来的位置。此题可解。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
 
 
int n,q;
int a[200001];
int de[200001];
 
 
int tree[200001*4];
 
void build(int now,int l,int r){
	if(l==r){
		tree[now]=de[l];
		return ;
	}
	int mid=(l+r)/2;
	build(now*2,l,mid);
	build(now*2+1,mid+1,r);
	tree[now]=max(tree[now*2],tree[now*2+1]);
	
}
 
void updata(int now,int l,int r,int num1,int num2){
	if(num1<l||num1>r){
		return;
	}
	if(l==r){
		tree[now]=num2;
		return ;
	}
	int mid=(l+r)/2;
	updata(now*2,l,mid,num1,num2);
	updata(now*2+1,mid+1,r,num1,num2);
	tree[now]=max(tree[now*2],tree[now*2+1]);	
}
 
int query(int now,int l,int r,int L,int R){
	if(r<L||l>R){
		return 0;
	}
	if(L<=l&&r<=R){
		return tree[now];
	}
	int mid=(l+r)/2;
	
	return max(query(now*2,l,mid,L,R),query(now*2+1,mid+1,r,L,R));
	
	
}
 
 
 
 
int read(){
	char c=getchar();
	int num=0;
	while(c>'9'||c<'0'){
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		num=num*10+c-'0';
		c=getchar();
	}
	return num;
}
int main(){
	int t,sb1,sb2;
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	for(int i=1;i<=n;i++){
		de[i]=abs(a[i]-a[i-1]);
	}
 
	if(n==1){
		q=read();
		for(int j=1;j<=q;j++){
			t=read();
			sb1=read();
			sb2=read();	
			if(t==2){
				printf("1\n");
			}	
		}
		return 0;
	}	
	
	build(1,2,n);
	
	
	q=read();
	for(int i=1;i<=q;i++){
		t=read();
		sb1=read();
		sb2=read();
		if(t==1){
			a[sb1]=sb2;
			if(sb1!=1){
				updata(1,2,n,sb1,abs(a[sb1]-a[sb1-1]));		
			}
			if(sb1!=n){
				updata(1,2,n,sb1+1,abs(a[sb1+1]-a[sb1]));		
			}
	
 
		}
		else{
			int l=sb1,r=n;
			int mid;
			int ans=sb1;
			while(l<=r){
				mid=(l+r)/2;
				if(query(1,2,n,sb1+1,mid)<=sb2){
					l=mid+1;
					ans=mid;
				}else{
					r=mid-1;
				}
			}
			printf("%d\n",ans);
			
		}
	}
	
	
	
	
	
	
	
	
	
	
}

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

隐藏