洛谷 P3616 富金森林公园 [树状数组]

传送门

维护一个山脉，单点修改，查询有多少山峰高出水面

---

我是沙茶沙茶题都不会做只想到无修改可以用扫描线

答案就是所有比水面高的-相邻都比水面高的啊

因为没有区间询问写个$BIT$都可以

有区间询问？可以考虑主席树吧

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const int N=2e5+,M=6e5+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,Q,mp[M],m,a[N];

void iniMP(){

    sort(mp+,mp++m);

    int p=;

    mp[++p]=mp[];

    for(int i=;i<=m;i++) if(mp[i]!=mp[i-]) mp[++p]=mp[i];

    m=p;

}

int Bin(int v){

    int l=,r=m;

    while(l<=r){

        int mid=(l+r)>>;

        if(v==mp[mid]) return mid;

        else if(v<mp[mid]) r=mid-;

        else l=mid+;

    }

    return ;

}

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=;

    for(;p<=m;p+=(p&-p)) re+=c[p];

    return re;

}

int main(){

    freopen("in","r",stdin);

    n=read();Q=read();

    for(int i=;i<=n;i++) mp[++m]=a[i]=read();

    for(int i=;i<=Q;i++){

        q[i].op=read();

        if(q[i].op==) mp[++m]=q[i].h=read();

        else q[i].p=read(),mp[++m]=q[i].h=read();

    }//puts("hi");

    iniMP();

    for(int i=;i<=n;i++) a[i]=Bin(a[i]),add(c1,a[i],),add(c2,min(a[i-],a[i]),);

    //for(int i=1;i<=n;i++) printf("%d ",a[i]);puts("");

    for(int i=;i<=Q;i++){

        q[i].h=Bin(q[i].h);

        if(q[i].op==) printf("%d\n",sum(c1,q[i].h)-sum(c2,q[i].h));

        else{

            int id=q[i].p;

            add(c1,a[id],-);add(c2,min(a[id-],a[id]),-);

            if(id!=n) add(c2,min(a[id],a[id+]),-);

            a[id]=q[i].h;

            add(c1,a[id],);add(c2,min(a[id-],a[id]),);

            if(id!=n) add(c2,min(a[id],a[id+]),);

        }

    }

}