维护一个山脉，单点修改，查询有多少山峰高出水面
我是沙茶沙茶题都不会做只想到无修改可以用扫描线
答案就是所有比水面高的-相邻都比水面高的啊
因为没有区间询问写个$BIT$都可以
有区间询问？可以考虑主席树吧
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int N=2e5+5,M=6e5+5; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,Q,mp[M],m,a[N]; void iniMP(){ sort(mp+1,mp+1+m); int p=0; mp[++p]=mp[1]; for(int i=2;i<=m;i++) if(mp[i]!=mp[i-1]) mp[++p]=mp[i]; m=p; } int Bin(int v){ int l=1,r=m; while(l<=r){ int mid=(l+r)>>1; if(v==mp[mid]) return mid; else if(v<mp[mid]) r=mid-1; else l=mid+1; } return 0; } struct Quer{ int op,h,p; }q[N]; int c1[M],c2[M]; inline void add(int *c,int p,int v){for(;p;p-=(p&-p)) c[p]+=v;} inline int sum(int *c,int p){ int re=0; for(;p<=m;p+=(p&-p)) re+=c[p]; return re; } int main(){ freopen("in","r",stdin); n=read();Q=read(); for(int i=1;i<=n;i++) mp[++m]=a[i]=read(); for(int i=1;i<=Q;i++){ q[i].op=read(); if(q[i].op==1) mp[++m]=q[i].h=read(); else q[i].p=read(),mp[++m]=q[i].h=read(); }//puts("hi"); iniMP(); for(int i=1;i<=n;i++) a[i]=Bin(a[i]),add(c1,a[i],1),add(c2,min(a[i-1],a[i]),1); //for(int i=1;i<=n;i++) printf("%d ",a[i]);puts(""); for(int i=1;i<=Q;i++){ q[i].h=Bin(q[i].h); if(q[i].op==1) printf("%d ",sum(c1,q[i].h)-sum(c2,q[i].h)); else{ int id=q[i].p; add(c1,a[id],-1);add(c2,min(a[id-1],a[id]),-1); if(id!=n) add(c2,min(a[id],a[id+1]),-1); a[id]=q[i].h; add(c1,a[id],1);add(c2,min(a[id-1],a[id]),1); if(id!=n) add(c2,min(a[id],a[id+1]),1); } } }