【AtCoder Grand 017C】Snuke and Spells 题解

题目大意

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

  \\~     \\~     \\~  

题解

       ~~~~~~       日常被欺诈。

       ~~~~~~       如果数字 $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); } }