← 返回题目列表

Codeforces · 1705/E

E. 马克和科罗教授

中文机器翻译题面 查看原题

睡觉前看了一部动漫后,马克梦见站在一间旧教室里,黑板上有一系列 $$$n$$$ 正整数 $$$a_1, a_2,\dots,a_n$$$。

然后,Koro教授进来了。他可以执行以下操作:

- 选择一个在棋盘上至少出现 $$$2$$$ 次的整数 $$$x$$$,
- 删除那些 $$$2$$$ 的出现,并且
- 在黑板上写下$$$x+1$$$。

Koro教授随后向Mark提出了一个问题:“经过一些操作后,棋盘上可能出现的最大数字是多少?”

马克很快就解决了这道题,但他仍然比Koro教授慢。因此,科罗教授决定给马克额外的挑战。他将更新初始整数序列 $$$q$$$ 次。每次,他都会选择正整数$$$k$$$和$$$l$$$,然后将$$$a_k$$$更改为$$$l$$$。每次更新后,他都会再次问马克同样的问题。

帮助马克比科罗教授更快地回答这些问题!

请注意,更新是持久的。对序列 $$$a$$$ 所做的更改将在处理将来的更新时应用。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2\leq n\leq 2\cdot 10^5$$$, $$$1\leq q\leq 2\cdot 10^5$$$) — 分别是序列 $$$a$$$ 的长度和更新次数。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\dots,a_n$$$ ($$$1\leq a_i\leq 2\cdot 10^5$$$)

然后是 $$$q$$$ 行,每行由两个整数 $$$k$$$ 和 $$$l$$$ ($$$1\leq k\leq n$$$, $$$1\leq l\leq 2\cdot 10^5$$$) 组成,告诉将 $$$a_k$$$ 更新为 $$$l$$$。

输出

打印 $$$q$$$ 行。第 $$$i$$$ 行应包含一个整数 - 第 $$$i$$$ 更新后的答案。

示例

输入 #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

注意

在第一个示例测试中,程序必须进行 $$$4$$$ 更新。

第一次更新后的序列是$$$[2,3,2,4,5]$$$。实现以下数字 $$$6$$$ 的一个操作序列。

- 最初,黑板上有数字$$$[2,3,2,4,5]$$$。
- 擦除 $$$2$$$ 的两个副本并写入 $$$3$$$,产生 $$$[3,4,5,\color{red}{3}]$$$。
- 擦除 $$$3$$$ 的两个副本并写入 $$$4$$$,产生 $$$[4,5,\color{red}{4}]$$$。
- 擦除 $$$4$$$ 的两个副本并写入 $$$5$$$,产生 $$$[5,\color{red}{5}]$$$。
- 擦除 $$$5$$$ 的两个副本并写入 $$$6$$$,产生 $$$[\color{red}{6}]$$$。

然后,在第二次更新中,数组更改为 $$$[2,3,2,4,3]$$$。这次,马克无法达到 $$$6$$$。然而,Mark 可以用来实现 $$$5$$$ 的一个序列如下所示。

- 最初,黑板上有$$$[2,3,2,4,3]$$$。
- 擦除 $$$2$$$ 的两个副本并写入 $$$3$$$,产生 $$$[3,4,3,\color{red}{3}]$$$。
- 擦除 $$$3$$$ 的两个副本并写入 $$$4$$$,产生 $$$[3,4,\color{red}{4}]$$$。
- 擦除 $$$4$$$ 的两个副本并写入 $$$5$$$,产生 $$$[3,\color{red}{5}]$$$。

在第三次更新中,数组更改为$$$[2,3,2,1,3]$$$。下面显示了实现 $$$4$$$ 的一种方法。

- 最初,黑板上有$$$[2,3,2,1,3]$$$。
- 擦除 $$$3$$$ 的两个副本并写入 $$$4$$$,产生 $$$[2,2,1,\color{red}{4}]$$$。