A15199 | Mark and Professor Koro
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
After watching a certain anime before going to sleep, Mark dreams of standing in an old classroom with a blackboard that has a sequence of $n$ positive integers $a_1, a_2,\dots,a_n$ on it.
Then, professor Koro comes in. He can perform the following operation:
- select an integer $x$ that appears at least $2$ times on the board,
- erase those $2$ appearances, and
- write $x+1$ on the board.
Professor Koro then asks Mark the question, "what is the maximum possible number that could appear on the board after some operations?"
Mark quickly solves this question, but he is still slower than professor Koro. Thus, professor Koro decides to give Mark additional challenges. He will update the initial sequence of integers $q$ times. Each time, he will choose positive integers $k$ and $l$ , then change $a_k$ to $l$ . After each update, he will ask Mark the same question again.
Help Mark answer these questions faster than Professor Koro!
Note that the updates are persistent. Changes made to the sequence $a$ will apply when processing future updates.
Then, professor Koro comes in. He can perform the following operation:
- select an integer $x$ that appears at least $2$ times on the board,
- erase those $2$ appearances, and
- write $x+1$ on the board.
Professor Koro then asks Mark the question, "what is the maximum possible number that could appear on the board after some operations?"
Mark quickly solves this question, but he is still slower than professor Koro. Thus, professor Koro decides to give Mark additional challenges. He will update the initial sequence of integers $q$ times. Each time, he will choose positive integers $k$ and $l$ , then change $a_k$ to $l$ . After each update, he will ask Mark the same question again.
Help Mark answer these questions faster than Professor Koro!
Note that the updates are persistent. Changes made to the sequence $a$ will apply when processing future updates.
输入格式
The first line of the input contains two integers $n$ and $q$ ( $2\leq n\leq 2\cdot 10^5$ , $1\leq q\leq 2\cdot 10^5$ ) — the length of the sequence $a$ and the number of updates, respectively.
The second line contains $n$ integers $a_1,a_2,\dots,a_n$ ( $1\leq a_i\leq 2\cdot 10^5$ )
Then, $q$ lines follow, each consisting of two integers $k$ and $l$ ( $1\leq k\leq n$ , $1\leq l\leq 2\cdot 10^5$ ), telling to update $a_k$ to $l$ .
The second line contains $n$ integers $a_1,a_2,\dots,a_n$ ( $1\leq a_i\leq 2\cdot 10^5$ )
Then, $q$ lines follow, each consisting of two integers $k$ and $l$ ( $1\leq k\leq n$ , $1\leq l\leq 2\cdot 10^5$ ), telling to update $a_k$ to $l$ .
输出格式
Print $q$ lines. The $i$ -th line should consist of a single integer — the answer after the $i$ -th update.
输入输出样例
输入 #1
5 4 2 2 2 4 5 2 3 5 3 4 1 1 4
输出 #1
6 5 4 5
输入 #2
2 1 200000 1 2 200000
输出 #2
200001
In the first example test, the program must proceed through $4$ updates.
The sequence after the first update is $[2,3,2,4,5]$ . One sequence of operations that achieves the number $6$ the following.
- Initially, the blackboard has numbers $[2,3,2,4,5]$ .
- Erase two copies of $2$ and write $3$ , yielding $[3,4,5,\color{red}{3}]$ .
- Erase two copies of $3$ and write $4$ , yielding $[4,5,\color{red}{4}]$ .
- Erase two copies of $4$ and write $5$ , yielding $[5,\color{red}{5}]$ .
- Erase two copies of $5$ and write $6$ , yielding $[\color{red}{6}]$ .
Then, in the second update, the array is changed to $[2,3,2,4,3]$ . This time, Mark cannot achieve $6$ . However, one sequence that Mark can use to achieve $5$ is shown below.
- Initially, the blackboard has $[2,3,2,4,3]$ .
- Erase two copies of $2$ and write $3$ , yielding $[3,4,3,\color{red}{3}]$ .
- Erase two copies of $3$ and write $4$ , yielding $[3,4,\color{red}{4}]$ .
- Erase two copies of $4$ and write $5$ , yielding $[3,\color{red}{5}]$ .
In the third update, the array is changed to $[2,3,2,1,3]$ . One way to achieve $4$ is shown below.
- Initially, the blackboard has $[2,3,2,1,3]$ .
- Erase two copies of $3$ and write $4$ , yielding $[2,2,1,\color{red}{4}]$ .
The sequence after the first update is $[2,3,2,4,5]$ . One sequence of operations that achieves the number $6$ the following.
- Initially, the blackboard has numbers $[2,3,2,4,5]$ .
- Erase two copies of $2$ and write $3$ , yielding $[3,4,5,\color{red}{3}]$ .
- Erase two copies of $3$ and write $4$ , yielding $[4,5,\color{red}{4}]$ .
- Erase two copies of $4$ and write $5$ , yielding $[5,\color{red}{5}]$ .
- Erase two copies of $5$ and write $6$ , yielding $[\color{red}{6}]$ .
Then, in the second update, the array is changed to $[2,3,2,4,3]$ . This time, Mark cannot achieve $6$ . However, one sequence that Mark can use to achieve $5$ is shown below.
- Initially, the blackboard has $[2,3,2,4,3]$ .
- Erase two copies of $2$ and write $3$ , yielding $[3,4,3,\color{red}{3}]$ .
- Erase two copies of $3$ and write $4$ , yielding $[3,4,\color{red}{4}]$ .
- Erase two copies of $4$ and write $5$ , yielding $[3,\color{red}{5}]$ .
In the third update, the array is changed to $[2,3,2,1,3]$ . One way to achieve $4$ is shown below.
- Initially, the blackboard has $[2,3,2,1,3]$ .
- Erase two copies of $3$ and write $4$ , yielding $[2,2,1,\color{red}{4}]$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted