题目背景
小 C 正在堆尸解隐藏曲的时候,他的好朋友小 A 随手就 Pure Memory 了。
小 C 也想成为像小 A 一样的 PM 大师,所以他需要你解决一个关于 PM(Prefix Mex)的问题。
题目描述
注意,本题对 mex 的定义与一般的定义不同。
对于可重集 S 定义 mex(S) 表示最小的 正整数 x 满足 x∉S。
对于给定的数组 a1,a2,…,an,保证 −1≤ai≤n,使用以下的方式生成数组 b1,b2,…,bn:
bi={aiai≠0mex({b1,b2,…,bi−1})ai=0
现在给定长度为 n 的数组 a1,a2,…,an,保证初始时 ai∈{−1,0} 且数组 a 不全为 0。
给定 q 次操作,每次操作给定三个整数 x,k,y,保证 1≤x,y≤n,ax≠0,−1≤k≤n 且 k≠0。表示先将 ax 修改为 k,然后你需要求出使用当前的数组 a 所生成的数组 b 中 by 的值。
注意,任意时刻为 0 的 ai 不会被修改,不为 0 的 ai 不会被修改为 0。
输入格式
第一行两个正整数 n,q。
第二行 n 个整数,描述 a1,a2,…,an,保证初始时 ai∈{−1,0} 且数组 a 不全为 0。
接下来 q 行,每行 3 个整数 x,k,y,描述一次操作。
输出格式
共 q 行,第 i 行输出一个整数表示使用第 i 次修改操作后的数组 a 所生成的数组 b 中 by 的值。
样例
输入样例 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% 的数据,保证 1≤n,q≤106,ai∈{−1,0},1≤x,y≤n,ax≠0,−1≤k≤n 且 k≠0。保证数组 a 不全为 0。
子任务编号 | 特殊性质 | 分值 |
---|---|---|
1 | n,q≤104 | 10 |
2 | 初始时序列 a 单调不降 | 10 |
3 | k≤100 | 10 |
4 | 序列 a 中 0 的数量 ≤100 | 10 |
5 | 每次修改前 ax=−1 | 30 |
6 | 无 | 30 |