题目链接：https://cn.vjudge.net/contest/283920#problem/J
题目大意：首先给你n个门的高度，然后q次询问，每一次询问包括两种操作，第一种操作是将当前的门的高度提高到某一个值，第二种操作是给你一个起点，以及最大的跨越高度d，问你最远能走到哪里（如果能从a到达b则说明|Ha-Hb|<=d）。
具体思路：用线段树维护每一个区间的最大值，对于操作1就是单点修改了，对于操作二的话，用二分+线段树的方法查询最远能到达的地方就可以了。
AC代码：
#include<iostream>
#include<stack>
#include<cstring>
#include<iomanip>
#include<stdio.h>
#include<algorithm>
#include<cmath>
using namespace std;
# define ll long long
# define lson l,m,rt<<
# define rson m+,r,rt<<|
const int maxn = 2e5+;
int tree[maxn<<],a[maxn];
int maxx;
void up(int rt)
{
tree[rt]=max(tree[rt<<],tree[rt<<|]);
}
void buildtree(int l,int r,int rt)
{
if(l==r)
{
tree[rt]=abs(a[l]-a[l+]);
return ;
}
int m=(l+r)>>;
buildtree(lson);
buildtree(rson);
up(rt);
}
void update(int l,int r,int rt,int pos)
{
if(l==r)
{
tree[rt]=abs(a[l+]-a[l]);
return ;
}
int m=(l+r)>>;
if(pos<=m)
update(lson,pos);
else
update(rson,pos);
up(rt);
}
void query(int l,int r,int rt,int L,int R)
{
if(L<=l&&R>=r)
{
maxx=max(maxx,tree[rt]);
return ;
}
int m=(l+r)>>;
if(L<=m)
query(lson,L,R);
if(R>m)
query(rson,L,R);
up(rt);
}
int Find(int n,int t2,int t3)
{
int l=t2,r=n;
int ans=n+;
while(l<=r)
{
int mid=(l+r)>>;
maxx=;
query(,n,,l,mid);
// cout<<l<<" "<<r<<" "<<maxx<<" "<<t3<<endl;
if(maxx<=t3)
{
l=mid+;
}
else
{
ans=mid;
r=mid-;
}
}
return ans;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=; i<=n; i++)
{
scanf("%d",&a[i]);
}
int q,t1,t2,t3;
if(n==){
scanf("%d",&q);
while(q--){
scanf("%d %d %d",&t1,&t2,&t3);
if(t1==){
a[t2]=t3;
}
else if(t1==){
printf("1\n");
}
}
}
else{
buildtree(,n-,); scanf("%d",&q);
while(q--)
{
scanf("%d %d %d",&t1,&t2,&t3);
// cout<<t1<<" "<<t2<<" "<<t3<<endl;
if(t1==)
{
a[t2]=t3;
if(t2->)
update(,n-,,t2-);
if(t2<=n-)
update(,n-,,t2);
}
else if(t1==)
{
int ans=Find(n-,t2,t3);
printf("%d\n",ans);
}
}
}
return ;
}