自动搬运

查看原文

来自洛谷，原作者为

	钰瑾_恋涵 菜死了

搬运于2025-08-24 22:34:46，当前版本为作者最后更新于2022-08-29 13:11:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接

题目大意：

给你 $n$ 个人的身高范围，一次操作可以将连续的一段人排除，但要求这些人身高没有交集，有 $Q$ 个询问，每个询问给定 $l$，$r$ 问最多需要几次操作可以将 $l - r$ 之间的人全部排除。

分析：

考虑贪心，对于一次操作，设其左端点为 $l$，那么我们一定会让右端点尽可能的大，所以 $r$ 选择身高无交集的最大的 $r$。

对于每一个 $l$ 们都求出它的 $r$，这一操作可以用数据结构去维护，我这里用的是单调队列加线段树，复杂度为 $O(n\log n)$。

另外身高很高啊，还要离散化。

然后整道题目就很清晰了，就相当于最少线段覆盖，这就是倍增优化 DP 的板子题了，点可以转成线段。

code

#include <bits/stdc++.h>

using namespace std;

typedef long long i64;

i64 read() {
	i64 x(0), f(0); char ch = getchar();
	while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
	return f ? -x : x;
}
int __stk[128], __len;
void put(i64 x) {
	if (x < 0) putchar('-'), x = -x;
	do { __stk[++__len] = x % 10, x /= 10; } while (x);
	while (__len) putchar(__stk[__len--] ^ 48);
}
const int N = 401010;
int n, q, cnt;
int L[N], R[N], c[N];
int f[N][22];

struct Tree {
	#define mid ((l + r) >> 1)
	#define ls (x << 1)
	#define rs (x << 1 | 1)
	int t[N << 4], tag[N << 4];
	void pushdown(int x) {
		if (tag[x]) {
			t[ls] += tag[x], tag[ls] += tag[x];
			t[rs] += tag[x], tag[rs] += tag[x];
			tag[x] = 0;
		}
	}
	void modify(int x, int l, int r, int L, int R, int v) {
		if (l >= L && r <= R) return t[x] += v, tag[x] += v, void();
		pushdown(x);
		if (mid >= L) modify(ls, l, mid, L, R, v);
		if (mid < R) modify(rs, mid + 1, r, L, R, v);
		t[x] = max(t[ls], t[rs]);
	}
	int ask(int x, int l, int r, int L, int R) {
		if (l >= L && r <= R) return t[x];
		pushdown(x); int ans = 0;
		if (mid >= L) ans = max(ans, ask(ls, l, mid, L, R));
		if (mid < R) ans = max(ans, ask(rs, mid + 1, r, L, R));
		return ans;
	}
}T;

signed main() {
//	freopen("osumnjiceni.in","r",stdin);
//	freopen("osumnjiceni.out","w",stdout);
	n = read();
	for (int i = 1; i <= n; ++i) {
		c[++cnt] = L[i] = read();
		c[++cnt] = R[i] = read(); 
	}
	sort(c + 1, c + cnt + 1), cnt = unique(c + 1, c + cnt + 1) - c - 1;
	for (int i = 1; i <= n; ++i) {
		L[i] = lower_bound(c + 1, c + cnt + 1, L[i]) - c;
		R[i] = lower_bound(c + 1, c + cnt + 1, R[i]) - c;
	}
	int p = 1;
	for (int i = 1; i <= n; ++i) {
		while (T.ask(1, 1, cnt, L[i], R[i])) {
			f[p - 1][0] = i - 1;
			T.modify(1, 1, cnt, L[p], R[p], -1), ++p;
		}
		T.modify(1, 1, cnt, L[i], R[i], 1);
	}
	while (p <= n + 1) f[p - 1][0] = n, ++p;
	for (int j = 1; j <= 20; ++j) 
		for (int i = 0; i <= n; ++i) 
			f[i][j] = f[f[i][j - 1]][j - 1];
	q = read();
	while (q--) {
		int l = read() - 1, r = read(), ans = 1;
		for (int i = 20; ~i; --i) if(f[l][i] < r) ans += 1 << i, l = f[l][i];
		put(ans), putchar('\n');
	}
	return 0;
}