← 返回题目列表

Codeforces · 2057/D

D. 礼品订购

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

“T一代”决定购买礼物以满足各种需求;因此,他们有 $$$n$$$ 不同的毛衣,编号从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 毛衣的尺寸为 $$$a_i$$$。现在他们需要将毛衣的一部分送去参加奥林匹克竞赛。毛衣必须适合尽可能多的人,但又不必带太多人。

他们需要选择两个索引 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) 来最大化等于 $$$$$$\operatorname{max} (a_l, a_{l + 1}, \ldots, a_r) - \operatorname{min} (a_l, a_{l + 1}, \ldots, a_r) - (r - l),$$$$$$ 即尺寸范围减去毛衣的数量。

有时毛衣的尺寸会发生变化;已知发生了$$$q$$$变化,在每次变化中,第$$$p$$$毛衣的尺码变为$$$x$$$。

帮助“T 一代”团队并确定所有可能的对 $$$(l, r)$$$ 最初以及每次尺寸更改后的最大便利性。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$)——毛衣的数量和尺寸变化的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 毛衣的尺寸。

每个测试用例的以下 $$$q$$$ 行均包含两个整数 $$$p$$$ 和 $$$x$$$ ($$$1 \le p \le n$$$, $$$1 \le x \le 10^9$$$) - 下一个大小更改。

保证所有测试用例中 $$$n$$$ 的值之和以及 $$$q$$$ 的值之和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,在任何操作之前以及每次大小更改之后输出所有可能对 $$$(l, r)$$$ 中便利性的最大值。

示例

输入 #1

3
2 2
1 10
1 10
2 2
5 3
1 2 3 4 5
3 7
1 4
5 2
8 5
7 4 2 4 8 2 1 4
5 4
1 10
3 2
8 11
7 7

输出 #1

8
0
7
0
4
4
4
5
3
6
6
9
7

注意

考虑第一个测试用例。

- 在进行任何更改之前,您可以拿走所有毛衣;那么方便性就等于 $$$\operatorname{max} (a_1, a_2) - \operatorname{min} (a_1, a_2) - (2 - 1) = 10 - 1 - 1 = 8$$$。
- 第一次查询后,两件毛衣的尺寸将等于$$$10$$$,您只能取第一件毛衣,方便等于$$$10 - 10 - 0 = 0$$$。
- 第二次查询后,第一件毛衣尺寸为$$$10$$$,第二件为$$$2$$$,可以拿走所有毛衣,方便等于 $$$\operatorname{max} (a_1, a_2) - \operatorname{min} (a_1, a_2) - (2 - 1) = 10 - 2 - 1 = 7$$$。