还有一天就考noip了,十分慌张。
考前最后一场模拟赛由yjq出题,感谢他的指导

如果来生

(e.pas/c/cpp)
【背景描述】
给定N个1到N的数, 重复以下操作:
设当前剩下k个数, 找到所有等于k的数, 把这些数全部删掉。
直到没有数或者不能再删数。
你想知道至少要修改这N个数中的多少个(修改之后每个数仍然必须从1到N), 使得可以删完这N个数。
我们还有M次修改操作, 每一次修改会把第Xi个数变成Yi, 每次修改完之后你都要对当前序列回答这个问题。 每次询问的操作不会真正实现,即对后面的询问没有影响。

【输入格式】
第一行两个整数N,M。
接下来一行N个整数, 第i个整数表示给出的第i个数。
接下来M行, 每行两个整数Xi, Yi 意义如题目所说。

【输出格式】
M行, 每行一个整数表示答案

【样例输入】
2 2
1 1
2 2
2 1

【样例输出】
0
1

【数据规模】
对于 15% 的数据,N, M ≤ 6.
对于 35% 的数据,N, M ≤ 20.
对于 55% 的数据,N, M ≤ 200。
对于 75% 的数据,N, M ≤ 2000.
对于 100% 的数据,N, M ≤ 200000.

用a数组记录每个数出现的次数,开一个数组b来存储每个数被覆盖的次数。每个数i可以分别覆盖max(1,i-a[i]+1)到i的所有的数一次。于是不难发现123456和333556的本质是一样的。如果一个数被覆盖过至少一次,那么就是可以直接不修改而通过;如果一个数没有被覆盖过,那么必须有一个其它的数被修改,修改次数+=1。在每次修改的时候直接判断有没有数的被覆盖情况改变即可。

还能遇见你

(f.pas/c/cpp)
【背景描述】
不想让各位在考前觉得难受,这道题就用来讲聊聊天吧。
其实认识你们也才一年多,我也只比你们大两届,说不定还没大到两岁。
我很想很想帮你们走的更远,更好,退一万步说不要有人因为OI反而路变窄了。
我也真的很想很想你们之中有人能补上学校这几年一切的一切的遗憾。
现在你们真的要代表整个学校,去面对接下来一年的旅途。可能我还是太幼稚了吧,竟然有点莫名的想哭。
也许你们已经知道,后面的路会更难走,坡会更陡,对于你们来说,我只能算一个过客,最多只能告诉你这个坡在哪里,你要往哪里走,但是之后,就只能靠你们自己了。
各位,保重。
这道题,送各位上路。

【输入格式】

【输出格式】
你期望的NOIP分数

【样例输出】
580

看了最后题过后真的很心酸……
本蒟蒻也只能打一个极其水的代码来向yjq致敬了

[]