题链：
树状数组，，，
本题思路挺巧妙。
考虑这种暴力算法：（设H[i]为i位置的高度,水面的高度为B）
从左枚举到右，如果 H[i-1]<B<=H[i]，那么就可以贡献答案，即 ANS++。
基于上述暴力，可以得出：
如果 H[i-1] < H[i]，且询问的 B 在这两个H值之间，则会贡献答案。
所以，用数据结构维护区间修改（把区间H[i-1]+1～H[i]的值加一）和单点查询（查询当前的水面高度B的ANS）即可。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 200500
using namespace std;
int H[MAXN],tmp[MAXN*3];
int N,M,tnt;
struct Question{
int a,b,c;
}Q[MAXN];
struct BIT{
int A[MAXN*3],len;
void Reset(int n){
len=n; memset(A,0,sizeof(A));
}
int Lowbit(int x){return x&-x;}
void Modify(int l,int r,int x){
r++;
while(l<=len) A[l]+=x,l+=Lowbit(l);
while(r<=len) A[r]-=x,r+=Lowbit(r);
}
int Query(int p){
static int ret; ret=0;
while(p) ret+=A[p],p-=Lowbit(p);
return ret;
}
}DT;
int main(){
scanf("%d%d",&N,&M); tmp[++tnt]=0;
for(int i=1;i<=N;i++) scanf("%d",&H[i]),tmp[++tnt]=H[i];
for(int i=1;i<=M;i++){
scanf("%d",&Q[i].a);
if(Q[i].a==1) scanf("%d",&Q[i].b),tmp[++tnt]=Q[i].b;
else scanf("%d%d",&Q[i].b,&Q[i].c),tmp[++tnt]=Q[i].c;
}
sort(tmp+1,tmp+tnt+1);
tnt=unique(tmp+1,tmp+tnt+1)-tmp-1;
DT.Reset(tnt); H[0]=lower_bound(tmp+1,tmp+tnt+11,H[0])-tmp;
for(int i=1;i<=N;i++){
H[i]=lower_bound(tmp+1,tmp+tnt+1,H[i])-tmp;
if(H[i]>H[i-1]) DT.Modify(H[i-1]+1,H[i],1);
}
for(int i=1;i<=M;i++){
if(Q[i].a==1){
Q[i].b=lower_bound(tmp+1,tmp+tnt+1,Q[i].b)-tmp;
printf("%d
",DT.Query(Q[i].b));
}
else{
if(H[Q[i].b]>H[Q[i].b-1]) DT.Modify(H[Q[i].b-1]+1,H[Q[i].b],-1);
if(H[Q[i].b+1]>H[Q[i].b]) DT.Modify(H[Q[i].b]+1,H[Q[i].b+1],-1);
H[Q[i].b]=lower_bound(tmp+1,tmp+tnt+1,Q[i].c)-tmp;
if(H[Q[i].b]>H[Q[i].b-1]) DT.Modify(H[Q[i].b-1]+1,H[Q[i].b],1);
if(H[Q[i].b+1]>H[Q[i].b]) DT.Modify(H[Q[i].b]+1,H[Q[i].b+1],1);
}
}
return 0;
}