AGC017C

lsj2009 · 2023-10-29 11:30:02 · 题解

人类智慧题。

如果说值为 x 的数出现了 c_x 次，则当序列长度剩余 x 时可以从 x 变成 x-c_x，则我们考虑连一条边 x-c_x，那么当所有线段依次首尾相接、从 n 到 1 时则有解。由于线段总长为 n，所以等价于 [1,n] 的区间被线段全部覆盖。

如果说我们执行一次 a_i 从 x 修改成 y 的操作，则从 x 的结尾的线段长度减一，从 y 结尾的线段长度加一，手摸一下可以得到答案为没有被覆盖的区间长度。

至于询问的修改的话，也是易维护的，不多赘述。

#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int N=2e5+5;
int cnt[N],d[N],a[N];
signed main() {
    int n,q;
    scanf("%d%d",&n,&q);
    rep(i,1,n) {
        scanf("%d",&a[i]);
        ++cnt[a[i]];
    }
    rep(i,1,n)
        ++d[max(i-cnt[i]+1,1)],--d[i+1];
    int res=0;
    rep(i,1,n)
        d[i]+=d[i-1],res+=d[i]==0;
    while(q--) {
        int p,val;
        scanf("%d%d",&p,&val);
        if(a[p]-cnt[a[p]]+1>=1) {
            if(!--d[a[p]-cnt[a[p]]+1])
                ++res;
        }
        --cnt[a[p]]; a[p]=val; ++cnt[a[p]];
        if(a[p]-cnt[a[p]]+1>=1) {
            if(!d[a[p]-cnt[a[p]]+1]++)
                --res;
        }
        printf("%d\n",res);
    }
    return 0;
}