Array and Segments (Hard version)

题意翻译

## 题目描述 给定你一个长度为 $n$ 的数组 $a$ ，再给定你 $m$ 对数字 $[l_i,r_i]$ 。你可以选择其中的几对数字作为两个端点，再将数组 $a$ 中的两个端点内的数字全部减一。（例如现有一对 $[l_i,r_i]$ 为 $[1,3]$ ，而数组 $a$ 为 ```1 2 3 4 5``` ，若使用这对 $[l_i,r_i]$ 数组就会变成 ``` 0 1 2 4 5 ```） 现在请你求出怎样使得数组 $a$ 中的最大值减去最小值最大。 ## 输入格式 - 第一行为 $n$ 和 $m$ - 第二行有 $n$ 个数字，表示数组 $a$ - 接下来的 $m$ 行，每行有两个数字，表示一对 $[l_i,r_i]$ 。 ## 输出格式 - 第一行表示更改后的数组 $a$ 中的最大值与最小值之差 - 第二行有一个整数 $k$，表示使用了多少对 $[l_i,r_i]$ 才让数组中最大值与最小值之差最大 - 第三行有 $k$ 个整数，表示你使用了哪些 $[l_i,r_i]$ （输出其的编号）。

题目描述

The only difference between easy and hard versions is a number of elements in the array. You are given an array $ a $ consisting of $ n $ integers. The value of the $ i $ -th element of the array is $ a_i $ . You are also given a set of $ m $ segments. The $ j $ -th segment is $ [l_j; r_j] $ , where $ 1 \le l_j \le r_j \le n $ . You can choose some subset of the given set of segments and decrease values on each of the chosen segments by one (independently). For example, if the initial array $ a = [0, 0, 0, 0, 0] $ and the given segments are $ [1; 3] $ and $ [2; 4] $ then you can choose both of them and the array will become $ b = [-1, -2, -2, -1, 0] $ . You have to choose some subset of the given segments (each segment can be chosen at most once) in such a way that if you apply this subset of segments to the array $ a $ and obtain the array $ b $ then the value $ \max\limits_{i=1}^{n}b_i - \min\limits_{i=1}^{n}b_i $ will be maximum possible. Note that you can choose the empty set. If there are multiple answers, you can print any. If you are Python programmer, consider using PyPy instead of Python when you submit your code.

输入输出格式

输入格式

The first line of the input contains two integers $ n $ and $ m $ ( $ 1 \le n \le 10^5, 0 \le m \le 300 $ ) — the length of the array $ a $ and the number of segments, respectively. The second line of the input contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ -10^6 \le a_i \le 10^6 $ ), where $ a_i $ is the value of the $ i $ -th element of the array $ a $ . The next $ m $ lines are contain two integers each. The $ j $ -th of them contains two integers $ l_j $ and $ r_j $ ( $ 1 \le l_j \le r_j \le n $ ), where $ l_j $ and $ r_j $ are the ends of the $ j $ -th segment.

输出格式

In the first line of the output print one integer $ d $ — the maximum possible value $ \max\limits_{i=1}^{n}b_i - \min\limits_{i=1}^{n}b_i $ if $ b $ is the array obtained by applying some subset of the given segments to the array $ a $ . In the second line of the output print one integer $ q $ ( $ 0 \le q \le m $ ) — the number of segments you apply. In the third line print $ q $ distinct integers $ c_1, c_2, \dots, c_q $ in any order ( $ 1 \le c_k \le m $ ) — indices of segments you apply to the array $ a $ in such a way that the value $ \max\limits_{i=1}^{n}b_i - \min\limits_{i=1}^{n}b_i $ of the obtained array $ b $ is maximum possible. If there are multiple answers, you can print any.

输入输出样例

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

说明

In the first example the obtained array $ b $ will be $ [0, -4, 1, 1, 2] $ so the answer is $ 6 $ . In the second example the obtained array $ b $ will be $ [2, -3, 1, -1, 4] $ so the answer is $ 7 $ . In the third example you cannot do anything so the answer is $ 0 $ .

题意翻译

## 题目描述 给定你一个长度为 $n$ 的数组 $a$ ，再给定你 $m$ 对数字 $[l_i,r_i]$ 。你可以选择其中的几对数字作为两个端点，再将数组 $a$ 中的两个端点内的数字全部减一。（例如现有一对 $[l_i,r_i]$ 为 $[1,3]$ ，而数组 $a$ 为 ```1 2 3 4 5``` ，若使用这对 $[l_i,r_i]$ 数组就会变成 ``` 0 1 2 4 5 ```） 现在请你求出怎样使得数组 $a$ 中的最大值减去最小值最大。 ## 输入格式 - 第一行为 $n$ 和 $m$ - 第二行有 $n$ 个数字，表示数组 $a$ - 接下来的 $m$ 行，每行有两个数字，表示一对 $[l_i,r_i]$ 。 ## 输出格式 - 第一行表示更改后的数组 $a$ 中的最大值与最小值之差 - 第二行有一个整数 $k$，表示使用了多少对 $[l_i,r_i]$ 才让数组中最大值与最小值之差最大 - 第三行有 $k$ 个整数，表示你使用了哪些 $[l_i,r_i]$ （输出其的编号）。