【AtCoder Grand 017C】Snuke and Spells 题解

题目大意

  有 $n$ 个球，每个球上有数字 $a_i$。
  游戏是这样的：若当前还剩 $k$ 个球，就把写有数字 $k$ 的球全部拿走，重复这个过程。你可以修改若干球上的数字，使得最后可以拿完所有的球。求最少修改多少个球。
  并且问题是动态的，有 $m$ 次操作，每次会修改一个球上的数字，每次修改完后问你游戏答案。
  $a_i \leq n \leq 2 \times 10^5,\ \ m \leq 2 \times 10^5$

$$\\$$ $$\\$$ $$\\$$

题解

  日常被欺诈。

  如果数字 $x$ 有 $y$ 个球，我们看成 $(x-y+1, x)$ 这样一条线段。那现在数轴上就有很多条线段，其中没被覆盖的位置数量就是答案。

  如何证明？
  首先这肯定是下界。
  其次我们能构造出一种方案使其可行。若当前数轴上有空位，那就说明别的地方肯定有重复覆盖的位置。重复覆盖要么是线段相交，要么是线段包含，而这两者都必定有线段的开头被重复覆盖，因此我们一定能找到这个开头，挖掉 $1$ 的长度来补数轴上的空位。
  因此这就是最优解。

代码

#include<cstdio>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

const int maxn=2e5+5;

int n,a[maxn],num[maxn];

int ans,cov[maxn];
void ADD(int x)
{
	if (x<=0) return;
	if (++cov[x]==1) ans++;
}
void DEC(int x)
{
	if (x<=0) return;
	if (--cov[x]==0) ans--;
}

int m;
int main()
{
	scanf("%d %d",&n,&m);
	fo(i,1,n)
	{
		scanf("%d",&a[i]);
		num[a[i]]++;
		ADD(a[i]-num[a[i]]+1);
	}
	
	while (m--)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		
		DEC(a[x]-num[a[x]]+1);
		num[a[x]]--;
		num[y]++;
		ADD(y-num[y]+1);
		a[x]=y;
		
		printf("%d\n",n-ans);
	}
}