题意

对于一个数列，有$2$种操作：

• $1 \ x$ 询问$\ge x$的连续段的个数
• $2 \ i \ x$ 将$a_i$的值修改为$x$

数据范围：$1 \le n,m \le 200000,1 \le a_i,x \le 10^9$

题解

首先对于一个询问考虑：将$\ge x$的数定义为$1$，$< x$的数定义为$0$；那么一个段的构成应为$$011 \dots 110$$即一个$01$+若干$11$+一个$10$，那么段的个数即为$01$或$10$的个数
如何统计这个数呢？记$\max(a[i],a[i-1])=1$的个数为$m$，$\min(a[i],a[i-1])=1$的个数为$n$，答案即为$\frac{n-m}{2}$
为什么呢？$m$代表$01,11,10$的数量，$n$代表$11$的数量，自然$n-m$就代表$01,10$的数量，而$01,10$成对出现，答案即为$\frac{n-m}{2}$
那么，$11$的贡献就为$1$，$01$或$10$的贡献就为$-1$
再来考虑多个询问：对于较大的$x$为$1$，那么对于较小的$x$显然也为$1$；所以我们在值域上建树状数组（虽然有$10^9$，但可以离散化），不过由于我们需要的是$\ge x$的信息，所以反着来
每次修改将初始的影响取消掉，修改值后再增添影响

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=200000+10;
int n,m;
int a[N];
struct Query{
    int op,i,x;
} q[N];
int tot;
int b[N<<1],T[N<<1];
inline int lowbit(int x){
    return x&-x;
}
inline void update(int p,int k){
    p=tot-p+1;
    for(;p<=tot;p+=lowbit(p))
        T[p]+=k;
}
inline int query(int p){
    p=tot-p+1;
    int res=0;
    for(;p;p-=lowbit(p))
        res+=T[p];
    return res;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[++tot]=a[i];
    }
    for(int i=1;i<=m;i++){
        scanf("%d",&q[i].op);
        if(q[i].op==2)
            scanf("%d",&q[i].i);
        scanf("%d",&q[i].x);
        b[++tot]=q[i].x;
    }
    sort(b+1,b+tot+1);
    tot=unique(b+1,b+tot+1)-b-1;
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+tot,a[i])-b;
    for(int i=1;i<=m;i++)
        q[i].x=lower_bound(b+1,b+tot+1,q[i].x)-b;
    for(int i=0;i<=n;i++){
        update(max(a[i],a[i+1]),+1);
        update(min(a[i],a[i+1]),-1);
    }
    for(int i=1;i<=m;i++){
        if(q[i].op==1)
            printf("%d\n",query(q[i].x)>>1);
        else{
            int j=q[i].i;
            update(max(a[j],a[j+1]),-1);
            update(max(a[j],a[j-1]),-1);
            update(min(a[j],a[j+1]),+1);
            update(min(a[j],a[j-1]),+1);
            a[j]=q[i].x;
            update(max(a[j],a[j+1]),+1);
            update(max(a[j],a[j-1]),+1);
            update(min(a[j],a[j+1]),-1);
            update(min(a[j],a[j-1]),-1);
        }
    }
    return 0;
}