我努力奔跑,只为追上曾经被寄予厚望的自己

正睿17提高3 雇佣妹抖

2018-11-04 13:49:22


题意:长度为 $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;
}