[BJOI2019] 删数

佚名 6年前 (2019-04-25) 随笔 1365人围观抢沙发百度已收录

题目的含义可以看做是以权值为下标的一些柱子,每个柱子的高度就是这个权值的出现的次数。

然后把这些柱子向左推倒,一个高度为h的柱子的影响范围为i−h+1∼i。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

那么答案就是查询1∼n的这段区间没有被覆盖的点的个数。

因为所有没有被覆盖的位置都需要且可以通过一次更改使得能被推倒。

考虑线段树维护这个东西。

需要支持区间加，区间查询最小值的个数。

对于全局加操作，可以看成询问的区间向反方向移动了一格。

那么，相应的把对应的区间加进去或删掉即可。

注意一下边界的细节。

#include<bits/stdc++.h>
#define N 1100000
#define L 770000
#define eps 1e-7
#define inf 1e9+7
#define db double
#define ll long long
#define ldb long double
using namespace std;
inline int read()
{
    char ch=0;
    int x=0,flag=1;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*flag;
}
int a[N];
map<int,int>cnt;
struct node{int x,y;};
node operator+(node a,node b)
{
    if(a.x<b.x)return a;
    if(a.x>b.x)return b;
    return {min(a.x,b.x),a.y+b.y};
}
struct Segment_Tree
{
    #define lson o<<1
    #define rson o<<1|1
    #define mid ((l+r)>>1)
    node f[N*4];int addv[N*4];
    inline void pushup(int o){f[o]=f[lson]+f[rson];}
    inline void pushdown(int o)
    {
        f[lson].x+=addv[o];addv[lson]+=addv[o];
        f[rson].x+=addv[o];addv[rson]+=addv[o];
        addv[o]=0;
    }
    void build(int o,int l,int r)
    {
        if(l==r)return (void)(f[o]={0,1});
        build(lson,l,mid);build(rson,mid+1,r);pushup(o);
    }
    void optadd(int o,int l,int r,int ql,int qr,int k)
    {
        if(ql>qr)return;
        if(ql<=l&&r<=qr)
        {
            f[o].x+=k;addv[o]+=k;return;
        }
        pushdown(o);
        if(ql<=mid)optadd(lson,l,mid,ql,qr,k);
        if(qr>mid)optadd(rson,mid+1,r,ql,qr,k);
        pushup(o); 
    }
    node query(int o,int l,int r,int ql,int qr)
    {
        if(ql<=l&&r<=qr)return f[o];
        pushdown(o);
        if(ql<=mid&&qr>mid)return query(lson,l,mid,ql,qr)+query(rson,mid+1,r,ql,qr);
        if(ql<=mid)return query(lson,l,mid,ql,qr);
        if(qr>mid)return query(rson,mid+1,r,ql,qr);
        return {0,0};
    }
}T;
int main()
{
    int n=read(),m=read();
    for(int i=1;i<=n;i++)a[i]=read(),cnt[a[i]]++;T.build(1,-L,+L);
    for(int i=1;i<=n;i++)T.optadd(1,-L,+L,i-cnt[i]+1,i,+1);
    for(int i=1,l=1,r=n,k=0;i<=m;i++)
    {
        int flag=read(),x=read();
        if(flag==0)
        {
            if(x==-1)
            {
                T.optadd(1,-L,+L,l-cnt[l]+1,l,-1);
                l++,r++,k--;
                T.optadd(1,-L,+L,r-cnt[r]+1,r,+1);
            }
            else
            {
                T.optadd(1,-L,+L,r-cnt[r]+1,r,-1);
                l--,r--,k++;
                T.optadd(1,-L,+L,l-cnt[l]+1,l,+1); 
            }
        }
        else
        {
            if(l<=a[flag]&&a[flag]<=r)
            T.optadd(1,-L,+L,a[flag]-cnt[a[flag]]+1,a[flag]-cnt[a[flag]]+1,-1);
            
            cnt[a[flag]]--;a[flag]=x-k;cnt[a[flag]]++;
            
            if(l<=a[flag]&&a[flag]<=r)
            T.optadd(1,-L,+L,a[flag]-cnt[a[flag]]+1,a[flag]-cnt[a[flag]]+1,+1); 
        }
        node ans=T.query(1,-L,+L,l,r);
        if(ans.x==0)printf("%d\n",ans.y);else printf("0\n");
    }
    return 0;
}