Codeforces 1108E2 Array and Segments (Hard version) 差分，暴力

发表于 2019-02-02 分类于算法阅读次数： 55 本文字数： 3.8k 阅读时长 ≈ 3 分钟

Description:

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 \leq l_{j} \leq r_{j} \leq 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}_{i = 1}^{n} b_{i} - {min}_{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. ### Input: The first line of the input contains two integers $n$ and $m$ ( $1 \leq n \leq 10^{5}, 0 \leq m \leq 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} \leq a_{i} \leq 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 \leq l_{j} \leq r_{j} \leq n$ ), where $l_{j}$ and $r_{j}$ are the ends of the $j$ -th segment.

Output

In the first line of the output print one integer $d$ — the maximum possible value ${max}_{i = 1}^{n} b_{i} - {min}_{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 \leq q \leq 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 \leq c_{k} \leq m$ ) — indices of segments you apply to the array $a$ in such a way that the value ${max}_{i = 1}^{n} b_{i} - {min}_{i = 1}^{n} b_{i}$ of the obtained array $b$ is maximum possible. If there are multiple answers, you can print any.

Sample Input:

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

Sample Output:

6 2 4 1

Sample Input:

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

Sample Output:

7 2 3 2

Sample Input:

1 0 1000000

Sample Output:

0 0

题目链接

题解:

有一个长为 $n$ 的数列，有 $m$ 个线段，每个线段将该线段区间的所有数减一，你可以选任意个线段，要求最大化极差并输出一种方案

这种极差的题一个套路是固定最大值求最小值

那么我们可以枚举每一个数作为最大值的方案，对不包含这个数的线段进行操作，然后找最大最小值即可，利用差分的思想单次操作可以 $O (1)$ , 最后查询极值 $O (n)$ , 这样我们就找到了一个 $O (n^{2})$ 的优秀算法，可以通过这题的简单版本

然后我们注意到线段数很少，只有 $300$ 个，那么我们可以将原数列分为至多 $600$ 段，每一段的数作为最大值时策略是相同的，我们就的到了 $O (n \cdot m + m^{2})$ 的算法，cf 机子上跑得飞快

另外，可以用线段树加速操作得到 $O (m l o g (n))$ 的做法

甚至可以将 $n$ 也变成 $m$ , 因为我们只关心每一段的极值，可以把原数列切成至多 $600$ 段，每一段记录最大最小值即可，复杂度为 $O (m^{2})$ , 不知道为什么评论指出这个算法的老哥的代码跑的还没我 $O (n \cdot m + m^{2})$ 快...

AC 代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, M = 310;

int n, a[N], b[N], ans, l[M], r[M], m, rec, cnt;
set<int> key;


int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) 
		scanf("%d", &a[i]);
	for(int i = 1; i <= m; ++i) {
		scanf("%d%d", &l[i], &r[i]);
		key.insert(l[i]);
		key.insert(r[i] + 1);
	}
	ans = *max_element(a + 1, a + n + 1) - *min_element(a + 1, a + n + 1);	
	for(auto it = key.begin(); it != key.end(); ++it) {
		int i = *it; ++cnt;
		memset(b, 0, sizeof(b));
		int mx = -1e9, mn = 1e9, sum = 0;
		for(int j = 1; j <= m; ++j) {
			if(l[j] <= i && i <= r[j]) continue;
			b[l[j]]--, b[r[j] + 1]++;
		}
		for(int j = 1; j <= n; ++j) {
			sum += b[j];
			mx = max(mx, a[j] + sum);
			mn = min(mn, a[j] + sum);
		}
		if(mx - mn > ans) {
			rec = i;
			ans = mx - mn;
		}
	}	
	printf("%d\n", ans);
	if(rec) {
		vector<int> res;
		for(int i = 1; i <= m; ++i) {
			if(l[i] <= rec && rec <= r[i]) continue;
			res.push_back(i);
		}
		printf("%d\n", (int)res.size());
		for(int i = 0; i < res.size(); ++i)
			printf("%d%c", res[i], " \n"[i == res.size() - 1]);
	}
	else
		puts("0\n");
	return 0;
}