← 返回题目列表

Codeforces · 1982/F

F. 再次排序问题

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

您有一个包含 $$$n$$$ 元素的数组 $$$a$$$。数组还有 $$$q$$$ 修改。在第一次修改之前和每次修改之后,您希望了解以下信息:

为了使数组 $$$a$$$ 完全按非降序排序,需要按非降序排序的最小长度子数组是多少?

更正式地说,您想要选择数组 $$$(l, r)$$$ 的子数组,其最小值为 $$$r - l + 1$$$。之后,您将对元素 $$$a_{l}、a_{l + 1}、\ldots、a_{r}$$$ 进行排序,并希望条件 $$$a_{i} \le a_{i + 1}$$$ 对所有 $$$1 \le i < n$$$ 成立。如果数组已经按非降序排序,则 $$$l$$$ 和 $$$r$$$ 应被视为等于 $$$-1$$$。

请注意,找到这样的 $$$(l, r)$$$ 不会以任何方式更改数组。修改本身采用以下形式:为给定的 $$$pos$$$ 和 $$$x$$$ 分配 $$$a_{pos} = x$$$。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^{5}$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_{i}$$$ ($$$0 \le |a_{i}| \le 10^{9}$$$) — 数组 $$$a$$$ 的初始元素。

每个测试用例的第三行包含一个数字 $$$q$$$ ($$$0 \le q \le 5 \cdot 10^{5}$$$) — 数组的修改次数。

每个测试用例的以下 $$$q$$$ 行包含两个整数 $$$pos_{i}$$$ ($$$1 \le pos_{i} \le n$$$) 和 $$$val_{i}$$$ ($$$0 \le |val_{i}| \le 10^{9}$$$) - 这意味着对于第 $$$i$$$ 次修改, $$$a_{pos_{i}}$$$ 被分配值$$$val_{i}$$$。

保证所有测试用例的$$$n$$$之和与$$$q$$$之和不超过$$$5 \cdot 10^{5}$$$。

输出

对于每个测试用例,输出 $$$q + 1$$$ 行。每行应包含 $$$2$$$ 整数 $$$l, r$$$ — 最小子数组的边界,这样对其进行排序将使数组 $$$a$$$ 完全排序。如果 $$$a$$$ 已经排序,则输出 $$$l = -1$$$, $$$r = -1$$$。

示例

输入 #1

2
5
2 2 3 4 5
3
2 1
4 1
1 1
5
1 2 3 4 5
9
1 4
2 3
5 2
3 1
1 1
5 1
4 1
3 1
2 1

输出 #1

-1 -1
1 2
1 4
3 4
-1 -1
1 3
1 3
1 5
1 5
2 5
2 5
2 5
2 5
-1 -1

注意

让我们考虑第一个测试用例:

- 最初,数组按非降序排序:$$$[2, 2, 3, 4, 5]$$$
- 第一个查询后,数组如下所示:$$$[\color{red}{2}, \color{red}{1}, 3, 4, 5]$$$。
- 第二次查询后,数组如下所示:$$$[\color{red}{2}, \color{red}{1}, \color{red}{3}, \color{red}{1}, 5]$$$。
- 第三次查询后,数组如下所示:$$$[1, 1, \color{red}{3}, \color{red}{1}, 5]$$$。

红色段表示需要排序的子数组,以便整个数组按非降序排序。