AtCoder GrandContest017 C Snuke and Spells

考试时当然是自己没有做出来啦。

这个题转化为较为明显的语言就是,给定一个序列,每次在进行特定的修改后,当前若有$k$个球,则会将所有编号为$k$的球全部消掉,有个家伙想要消掉所有的球,但这有可能是行不通的,给定球数字的时间顺序以及变化,问每次变化最小修改几次。

好像前几页的提交中有很多使用了线段树等结构,主要学习了tourist神犇的提交,然后仔细一想发现这样的解法好妙QWQ

我们如何得出一个序列能否修改/不修改,或者修改几次达到全消的目的呢?比如给定一个可以的例子:
$$1,3,3,6,6,6$$
第一次我们消掉所有$6$以后,正好剩余$3$个球,可以消掉所有$3$,接下来剩下一个球为$1$,自然可以消去,那么$6$影响的区间就是$[4,6]$下标范围的数,同理$3$为$[2,3]$,$1$为$[1,1]$,这些区间覆盖了所有的球,于是是可以成立的。

然后对于不能够全消完的样例:$2,3,4,5,5$,为什么消不完呢?$5$对应$[4,5]$,然后$4$对应$[3,3]$(这明显gg,$4$本身就消不掉),$3$对应$[3,3]$,$2$对应$[2,2]$,这样会发现下标$3$被多个区间覆盖,而$1$却没有被任何区间覆盖。多举几个例子就会发现没有被任何区间覆盖的下标/被重复覆盖的下标就是答案,因为这些数是肯定要被修改的(否则至少在当前的决策下不能满足该标号的球全被消掉)。

我们只需要先排序好这个序列,再处理出没有被覆盖的下标个数,输出即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
inline int readint()
{
char c;int tmp=0,x=1;c=getchar();
while(!isdigit(c)){if(c=='-') x=-1;c=getchar();}
while(isdigit(c)){tmp=tmp*10+c-'0';c=getchar();}
return tmp*x;
}
const int maxn=200000+5;
int a[maxn],x[maxn],y[maxn],cnt[maxn],b[maxn];
int n,m;
int main()
{
n=readint(),m=readint();
int emp=n;
for(int i=1;i<=n;i++)
{
a[i]=readint();
cnt[a[i]]++;
int pos=a[i]-cnt[a[i]]+1;
if(pos>=1 && (b[pos]++) ==0) emp--;
}
for(int i=1;i<=m;i++)
{
x[i]=readint(),y[i]=readint();
int pos=a[x[i]]-cnt[a[x[i]]]+1;cnt[a[x[i]]]--;
if(pos>=1 && (--b[pos])==0) emp++;
cnt[a[x[i]]=y[i]]++;pos=y[i]-cnt[y[i]]+1;
if(pos>=1 && (b[pos]++)==0) emp--;
printf("%d\n",emp);
}
return 0;
}