← 返回题目列表

Codeforces · 1108/E2

E2. 数组和段(硬版本)

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

简单版本和困难版本之间的唯一区别是数组中的元素数量。

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。数组中第 $$$i$$$ 元素的值为 $$$a_i$$$。

您还获得了一组 $$$m$$$ 段。第$$$j$$$段是$$$[l_j; r_j]$$$,其中 $$$1 \le l_j \le r_j \le n$$$。

您可以选择给定段集的某个子集,并将每个选定段的值减一(独立)。例如,如果初始数组 $$$a = [0, 0, 0, 0, 0]$$$ 并且给定的段是 $$$[1; 3]$$$ 和 $$$[2; 4]$$$ 那么你可以同时选择它们,数组将变为 $$$b = [-1, -2, -2, -1, 0]$$$。

您必须选择给定段的某个子集(每个段最多只能选择一次),如果您将此段子集应用于数组 $$$a$$$ 并获得数组 $$$b$$$,则值 $$$\max\limits_{i=1}^{n}b_i - \min\limits_{i=1}^{n}b_i$$$ 将是可能的最大值。

请注意,您可以选择空集。

如果有多个答案,您可以打印任何答案。

如果您是 Python 程序员,请在提交代码时考虑使用 PyPy 而不是 Python。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^5, 0 \le m \le 300$$$) — 分别是数组 $$$a$$$ 的长度和段数。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$-10^6 \le a_i \le 10^6$$$),其中 $$$a_i$$$ 是数组 $$$a$$$ 的第 $$$i$$$ 个元素的值。

接下来的 $$$m$$$ 行每行包含两个整数。其中第 $$$j$$$ 包含两个整数 $$$l_j$$$ 和 $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$),其中 $$$l_j$$$ 和 $$$r_j$$$ 是第 $$$j$$$ 段的末尾。

输出

在输出的第一行打印一个整数 $$$d$$$ — 最大可能值 $$$\max\limits_{i=1}^{n}b_i - \min\limits_{i=1}^{n}b_i$$$ 如果 $$$b$$$ 是通过将给定段的某些子集应用于数组 $$$a$$$ 获得的数组。

在输出的第二行打印一个整数 $$$q$$$ ($$$0 \le q \le m$$$) — 您应用的段数。

在第三行中以任意顺序打印 $$$q$$$ 不同的整数 $$$c_1, c_2, \dots, c_q$$$ ($$$1 \le c_k \le m$$$) — 应用于数组 $$$a$$$ 的段索引,使得值 $$$\max\limits_{i=1}^{n}b_i -所获得的数组 $$$b$$$ 的 \min\limits_{i=1}^{n}b_i$$$ 是最大可能的。

如果有多个答案,您可以打印任何答案。

示例

输入 #1

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

输出 #1

6
2
4 1

输入 #2

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

输出 #2

7
2
3 2

输入 #3

1 0
1000000

输出 #3

0
0

注意

在第一个示例中,获得的数组 $$$b$$$ 将是 $$$[0, -4, 1, 1, 2]$$$,所以答案是 $$$6$$$。

在第二个示例中,获得的数组 $$$b$$$ 将是 $$$[2, -3, 1, -1, 4]$$$,因此答案是 $$$7$$$。

在第三个示例中,您无法执行任何操作,因此答案是 $$$0$$$。