Luogu4064 [JXOI2017]加法

tony102

2021 年 02 月 18 日

1242 次浏览

暂无评论

876字数

题解

[Link](https://www.luogu.com.cn/problem/P4064)

## Sol

**总结：对于一类用贪心解决选一些区间来覆盖点（对点进行操作）的问题，可以贪心地考虑选的区间尽量往右边多贡献一点。**

现在的问题就是，给你了一些区间$[l_i,r_i]$ 和一个增加值 $val$，每个区间仅可以被选择一次，每次操作都选定一个区间并在序列上对这个区间内的数都加上$val$，现在要操作后的序列的最小值尽可能的大。只可以操作$k$次

首先看到最大化最小值这种字眼，就要二分一下这个答案。最优化问题改成判定性问题很常见。

还是对给你的区间按照左端点排序。那么现在从左往右操作。我们希望每次选定的区间右端点尽可能靠右，所以就吧区间加入一个大根堆里面，按照右端点排序即可。

特别注意的是，判定的时候一个点它可能加一次还是不满足，但是它有可能被多个区间覆盖。那么就while下去就可以了（这个bug我改了很久。

## Code

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

const int SIZE = 4e5 + 5;
const int inf = 0x7f7f7f7f;

int T, n, m, k, p;
int a[SIZE], tree[SIZE];

struct node {
	int l, r;
	bool operator< (const node &a) const {
		return r == a.r ? l < a.l : r < a.r;
	}
} ;
 
struct seg {
	int l, r;
	bool operator< (const seg &a) const {
		return l == a.l ? r < a.r : l < a.l;
	}
} b[SIZE];

namespace ae86 {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (!isdigit(c))b ^= c == '-', c = fetch();
		while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
}
using ae86::read;

#define lowbit(x) (x & (-x))

void modify(int pos, int val) {
	for ( ; pos <= n; pos += lowbit(pos)) tree[pos] += val;
}

int query(int pos) {
	int ans = 0;
	for ( ; pos; pos -= lowbit(pos)) ans += tree[pos];
	return ans;
}

int judge(int x) {
	std::priority_queue < node > q;
	memset(tree, 0, sizeof(tree));
	while (!q.empty()) q.pop();
	for (int i = 1; i <= n; ++ i) modify(i, a[i]), modify(i + 1, -a[i]);
	int cnt = 0;
	for (int i = 1, j = 1; i <= n; ++ i) {
		while (j <= m && b[j].l <= i) q.push((node) {b[j].l, b[j].r}), ++ j;
		while (query(i) < x) {
			if (q.empty()) return 0;
			node tmp = q.top(); q.pop();
			if (tmp.r < i) return 0;
			modify(tmp.l, p); modify(tmp.r + 1, -p); ++ cnt;
			if (cnt > k) return 0;
		}
	}
	return 1;
}

int main() {
	// freopen("code.in", "r", stdin);
	// freopen("code.out", "w", stdout);
	T = read();
	while (T --) {
		int l = inf, r = 0, mid = 0, ans = 0;
		n = read(), m = read(), k = read(), p = read();
		memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b));
		for (int i = 1; i <= n; ++ i) a[i] = read();
		for (int i = 1; i <= m; ++ i) b[i].l = read(), b[i].r = read();
		for (int i = 1; i <= n; ++ i) l = std::min(l, a[i]);
		std::sort(b + 1, b + m + 1);
		r = l + k * p;
		while (l <= r) {
			mid = (l + r) >> 1;
			if (judge(mid)) ans = std::max(ans,mid), l = mid + 1;
			else r = mid-1;
		}
		printf("%d\n", ans);
	}
	return 0;
}
```

最后修改：2023 年 09 月 20 日