AtCoder AGC017C Snuke and Spells

题目链接

https://atcoder.jp/contests/agc017/tasks/agc017_c

题解

很久前不会做看了题解，现在又看了一下，只想说，这种智商题真的杀我。。。

转化成如果现在有\(x\)个\(y\), 我们给区间\([y-x+1,y]\)都\(+1\)，那么答案就是区间内\(0\)的个数。。

于是就很好\(O(n)\)维护了。。然而我真的想不到。。。

代码

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#define llong long long

#define ldouble long double

#define uint unsigned int

#define ullong unsigned long long

#define udouble unsigned double

#define uldouble unsigned long double

#define modinc(x) {if(x>=P) x-=P;}

#define pii pair<int,int>

#define piii pair<pair<int,int>,int>

#define piiii pair<pair<int,int>,pair<int,int> >

#define pli pair<llong,int>

#define pll pair<llong,llong>

#define Memset(a,x) {memset(a,x,sizeof(a));}

using namespace std;

const int N = 2e5;

int cnt[N+2];

int a[N+2];

int num[N+2];

int n,q,ans;

int main()

{

	scanf("%d%d",&n,&q);

	for(int i=1; i<=n; i++) {scanf("%d",&a[i]); cnt[a[i]]++;}

	for(int i=1; i<=n; i++)

	{

		for(int j=max(i-cnt[i]+1,0); j<=i; j++) num[j]++;

	}

	for(int i=1; i<=n; i++) if(num[i]==0) ans++;

	for(int i=1; i<=q; i++)

	{

		int x,y; scanf("%d%d",&x,&y);

		cnt[a[x]]--; if(a[x]-cnt[a[x]]>0) {num[a[x]-cnt[a[x]]]--; if(num[a[x]-cnt[a[x]]]==0) ans++;}

		a[x] = y;

		if(y-cnt[y]>0) {if(num[y-cnt[y]]==0) ans--; num[y-cnt[y]]++;} cnt[y]++;

		printf("%d\n",ans);

	}

	return 0;

}