算法题

链接

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#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<lnum1>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<Ll>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);
  }
}