QOJ.ac

QOJ

Time Limit: 8 s Memory Limit: 512 MB Total points: 100
[+4]

# 9606. PM 大师

Statistics

题目背景

小 C 正在堆尸解隐藏曲的时候,他的好朋友小 A 随手就 Pure Memory 了。

小 C 也想成为像小 A 一样的 PM 大师,所以他需要你解决一个关于 PM(Prefix Mex)的问题。

题目描述

注意,本题对 mex 的定义与一般的定义不同。

对于可重集 S 定义 mex(S) 表示最小的 正整数 x 满足 xS

对于给定的数组 a1,a2,,an,保证 1ain,使用以下的方式生成数组 b1,b2,,bn

bi={aiai0mex({b1,b2,,bi1})ai=0

现在给定长度为 n 的数组 a1,a2,,an保证初始时 ai{1,0} 且数组 a 不全为 0

给定 q 次操作,每次操作给定三个整数 x,k,y,保证 1x,ynax01knk0。表示先将 ax 修改为 k,然后你需要求出使用当前的数组 a 所生成的数组 bby 的值。

注意,任意时刻为 0ai 不会被修改,不为 0ai 不会被修改为 0

输入格式

第一行两个正整数 n,q

第二行 n 个整数,描述 a1,a2,,an,保证初始时 ai{1,0} 且数组 a 不全为 0

接下来 q 行,每行 3 个整数 x,k,y,描述一次操作。

输出格式

q 行,第 i 行输出一个整数表示使用第 i 次修改操作后的数组 a 所生成的数组 bby 的值。

样例

输入样例 1

10 10
0 -1 0 0 -1 0 -1 -1 0 -1
7 5 9
7 5 1
10 8 4
7 10 1
8 -1 3
10 6 4
2 2 1
2 9 6
5 8 4
7 -1 9

输出样例 1

6
1
3
1
2
3
1
4
3
5

样例 2

见下发文件,其满足子任务 1 的限制。

数据范围

对于 100% 的数据,保证 1n,q106ai{1,0}1x,ynax01knk0。保证数组 a 不全为 0

子任务编号 特殊性质 分值
1 n,q104 10
2 初始时序列 a 单调不降 10
3 k100 10
4 序列 a0 的数量 100 10
5 每次修改前 ax=1 30
6 30