#PQJ1825x9606. QOJ 1825_9606

    ID: 2720 传统题 8000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2024-2025 集训队互测

QOJ 1825_9606

标题: PM 大师 - Problem - QOJ.ac

#9606. PM 大师

Statistics

The problem was used in the following contests:

题目背景

小 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