#P5324. [BJOI2019] 删数

    ID: 4982 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2019线段树各省省选北京O2优化Link-Cut Tree,LCT

[BJOI2019] 删数

题目描述

对于任意一个数列,如果能在有限次进行下列删数操作后将其删为空数列,则称这个数列可以删空。一次删数操作定义如下:

记当前数列长度为 kk ,则删掉数列中所有等于 kk 的数。

现有一个长度为 nn 的数列 aa,有 mm 次修改操作,第 ii 次修改后你要回答:
经过 ii 次修改后的数列 aa,至少还需要修改几个数才可删空?

每次修改操作为单点修改或数列整体加一或数列整体减一。

输入格式

第一行两个正整数 n,mn,m,分别表示数列长度、修改次数。
第二行有 nn 个正整数,表示数列 aa,即输入的第 ii 个数表示数列 aa 的第 ii 个数 aia_i

接下来 mm 行,每行两个整数 p,xp,x,表示一次修改操作。
1pn1\le p \le n 时,该操作为单点修改,将数列中第 pp 个数 apa_p 修改为 xx
p=0p=0 时,该操作为数列整体加 xx

输出格式

输出 mm 行,每行一个整数,第 ii 行表示前 ii 次修改后的答案。

3 9
1 2 3
1 1
0 1
0 1
0 1
2 2
3 2
0 -1
0 -1
0 -1
0
1
2
3
2
1
1
2
2

提示

样例解释(局部):
第一次修改后,数列为11 22 33,无需修改即可删空。
第四次修改后,数列为44 55 66,需要将三个数都改掉才可能删空。
第六次修改后,数列为44 22 22,将第一个数改成33即可删空。
第九次修改后,数列为11 1-1 1-1,可以将第二个数改成22、第三个数改成33来删空。

数据范围:
对于 100%100\% 的数据:
1n,m1500001\le n,m \le 150000
1ain1\le a_i \le n
0pn0\le p\le n
p>0p>0时,1xn1\le x \le n
p=0p=0时,x=1x=-111