Luogu

LOJ

分析

可以发现一个事情：我们把每个值的出现次数看成这个值对应的一根“柱子”的高度，然后把所有柱子向左推倒，那么最少需要修改的数的个数即为 $[1,n]$ 中未被柱子覆盖的数的个数。

于是可以直接用线段树维护，区间平移维护平移标记即可。在平移时两侧的柱子可能会进来、出去，需要及时加入和去除掉。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=450000+10,L=450000;
int R=150000;

int n,m,a[N],o[N];

#define ls (o<<1)
#define rs (o<<1|1)
pii minv[N<<2]; int addv[N<<2];
pii merge(pii a,pii b) {
    if (a.first!=b.first) return min(a,b);
    else return make_pair(a.first,a.second+b.second);
}
void pushup(int o) { minv[o]=merge(minv[ls],minv[rs]); }
void pushdown(int o) {
    if (addv[o]) {
        addv[ls]+=addv[o],minv[ls].first+=addv[o];
        addv[rs]+=addv[o],minv[rs].first+=addv[o];
        addv[o]=0;
    }
}
void build(int o,int l,int r) {
    if (l==r) { minv[o]=make_pair(0,1); return; }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(o);
}
void modify(int o,int l,int r,int ql,int qr,int w) {
    if (ql<=l&&r<=qr) { addv[o]+=w,minv[o].first+=w; return; }
    int mid=(l+r)>>1; pushdown(o);
    if (ql<=mid) modify(ls,l,mid,ql,qr,w);
    if (qr>mid) modify(rs,mid+1,r,ql,qr,w);
    pushup(o);
}
pii query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return minv[o];
    int mid=(l+r)>>1; pushdown(o);
    if (qr<=mid) return query(ls,l,mid,ql,qr);
    else if (ql>mid) return query(rs,mid+1,r,ql,qr);
    else return merge(query(ls,l,mid,ql,qr),query(rs,mid+1,r,ql,qr));
}
#undef ls
#undef rs

void add(int x) {
    ++o[x];
    if (x-R>=1&&x-R<=n) modify(1,0,L,x-o[x]+1,x-o[x]+1,1);
}
void del(int x) {
    if (x-R>=1&&x-R<=n) modify(1,0,L,x-o[x]+1,x-o[x]+1,-1);
    --o[x];
}

int main() {
    n=read(),m=read(); build(1,0,L);
    for (int i=1;i<=n;++i) a[i]=read()+R;
    for (int i=1;i<=n;++i) add(a[i]);
    while (m--) {
        int p=read(),x=read();
        if (p) del(a[p]),add(a[p]=x+R);
        else if (x==1) {
            if (o[n+R]) modify(1,0,L,n+R-o[n+R]+1,n+R,-1);
            --R;
            if (o[1+R]) modify(1,0,L,1+R-o[1+R]+1,1+R,1);
        } else {
            if (o[1+R]) modify(1,0,L,1+R-o[1+R]+1,1+R,-1);
            ++R;
            if (o[n+R]) modify(1,0,L,n+R-o[n+R]+1,n+R,1);
        }
        auto res=query(1,0,L,1+R,n+R);
        printf("%d\n",res.first?0:res.second);
    }
    return 0;
}