A6506 | 小枫的mex
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
小枫有一个长度为 $n$ 的序列 $a$ ，现在他想要对这个序列进行 $q$ 次查询，
第 $i$ 个查询的格式为：
对于每个查询：
+ 首先，把 $a_{pos}$ 修改为 $x$ 。这个修改是永久性的，即对后续的所有查询都有影响。
+ 然后，输出当前 $a$ 的 $mex$ 。
第 $i$ 个查询的格式为：
pos x对于每个查询：
+ 首先，把 $a_{pos}$ 修改为 $x$ 。这个修改是永久性的，即对后续的所有查询都有影响。
+ 然后，输出当前 $a$ 的 $mex$ 。
序列 $a$ 的 $mex$ 指的是 $a$ 中未出现的最小非负整数。
输入格式
第一行输入两个整数 $n,q$ $(1\leq n,q\leq 2\times 10^5)$ ，分别表示序列长度以及查询次数。
第二行输入 $n$ 个整数 $a_i$ $(0\leq a_i \leq 10^9)$ ，表示序列中第 $i$ 个整数的大小。
接下来 $q$ 行，每行输入一种查询，具体格式及含义见题面所示。
第二行输入 $n$ 个整数 $a_i$ $(0\leq a_i \leq 10^9)$ ，表示序列中第 $i$ 个整数的大小。
接下来 $q$ 行，每行输入一种查询，具体格式及含义见题面所示。
输出格式
一共输出 $q$ 行，对于每个查询单独输出一行一个整数表示答案。
输入输出样例
输入 #1
8 5 2 0 2 2 1 1 2 5 4 3 4 4 6 3 8 1000000000 2 1
输出 #1
4 3 6 5 0
样例解释
最初，数列 $A$ 为 $(2,0,2,2,1,1,2,5)$。本输入需要处理 $5$ 个查询。
- 第 $1$ 个查询将 $A_4=3$，此时 $A=(2,0,2,3,1,1,2,5)$。
- 此时 $A$ 的 $\rm{mex}$ 为 $4$。
- 第 $2$ 个查询将 $A_4=4$，此时 $A=(2,0,2,4,1,1,2,5)$。
- 此时 $A$ 的 $\rm{mex}$ 为 $3$。
- 第 $3$ 个查询将 $A_6=3$，此时 $A=(2,0,2,4,1,3,2,5)$。
- 此时 $A$ 的 $\rm{mex}$ 为 $6$。
- 第 $4$ 个查询将 $A_8=1000000000$，此时 $A=(2,0,2,4,1,3,2,1000000000)$。
- 此时 $A$ 的 $\rm{mex}$ 为 $5$。
- 第 $5$ 个查询将 $A_2=1$，此时 $A=(2,1,2,4,1,3,2,1000000000)$。
- 此时 $A$ 的 $\rm{mex}$ 为 $0$。
最初，数列 $A$ 为 $(2,0,2,2,1,1,2,5)$。本输入需要处理 $5$ 个查询。
- 第 $1$ 个查询将 $A_4=3$，此时 $A=(2,0,2,3,1,1,2,5)$。
- 此时 $A$ 的 $\rm{mex}$ 为 $4$。
- 第 $2$ 个查询将 $A_4=4$，此时 $A=(2,0,2,4,1,1,2,5)$。
- 此时 $A$ 的 $\rm{mex}$ 为 $3$。
- 第 $3$ 个查询将 $A_6=3$，此时 $A=(2,0,2,4,1,3,2,5)$。
- 此时 $A$ 的 $\rm{mex}$ 为 $6$。
- 第 $4$ 个查询将 $A_8=1000000000$，此时 $A=(2,0,2,4,1,3,2,1000000000)$。
- 此时 $A$ 的 $\rm{mex}$ 为 $5$。
- 第 $5$ 个查询将 $A_2=1$，此时 $A=(2,1,2,4,1,3,2,1000000000)$。
- 此时 $A$ 的 $\rm{mex}$ 为 $0$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？