题意:长度为$n$的序列$a$,有两种操作
- 招募$a_i>=k$的元素,两个元素在一个帮派当且仅当它们中间的所有元素都被招募。求这次招募的帮派数
- 把$a_x$修改成$c$
------------
第一种操作就是询问有多少个区间满足区间最小值$>=k$
维护$>=k$的元素总数$cnt1$,相邻的$>=k$的元素对数$cnt2$
那么答案就是$cnt1-cnt2$
这个可以用两个树状数组做到
修改的时候把对应的值$+1$或$-1$即可
```
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
const int N=2e5+5;
int n,m,a[N],b[N<<1],cnt;
struct node
{
int opt,x,val;
}q[N];
struct BIT
{
int c[N<<1];
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int k){for (;x<=cnt;x+=lowbit(x)) c[x]+=k;}
inline int query(int x,int res=0){for (;x;x-=lowbit(x)) res+=c[x]; return res;}
}T1,T2;
inline int read()
{
int x=0,w=1;
char c=getchar();
while (!isdigit(c)&&c!='-') c=getchar();
if (c=='-') c=getchar(),w=-1;
while (isdigit(c))
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*w;
}
int main()
{
n=cnt=read(),m=read();
for (reg int i=1;i<=n;i++) a[i]=b[i]=read();
for (reg int i=1;i<=m;i++)
{
int opt=read(),x=read();
if (opt==1) q[i]=(node){opt,0,x};
else q[i]=(node){opt,x,b[++cnt]=read()};
}
sort(b+1,b+cnt+1);
cnt=unique(b+1,b+cnt+1)-b-1;
for (reg int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b,T1.add(a[i],1);
for (reg int i=1;i<=m;i++) q[i].val=lower_bound(b+1,b+cnt+1,q[i].val)-b;
for (reg int i=1;i<n;i++) T2.add(min(a[i],a[i+1]),1);
for (reg int i=1;i<=m;i++)
{
if (q[i].opt>1)
{
int x=q[i].x;
T1.add(a[x],-1);
if (x>1) T2.add(min(a[x],a[x-1]),-1),T2.add(min(a[x-1],q[i].val),1);
if (x<n) T2.add(min(a[x],a[x+1]),-1),T2.add(min(a[x+1],q[i].val),1);
a[x]=q[i].val; T1.add(a[x],1);
}
else printf("%d\n",n-T1.query(q[i].val-1)-(n-1-T2.query(q[i].val-1)));
}
return 0;
}
```