Codeforces 1175E Minimal Segment Cover

题意：

有\(n\)条线段，区间为\([l_i, r_i]\)，每次询问\([x_i, y_i]\)，问要被覆盖最少要用多少条线段。

思路：

\(f[i][j]\)表示以\(i\)为左端点，用了\(2^j\)条线段，最远到哪里。

然后从大到小贪心即可，类似于倍增找LCA的过程。

代码：

#include <bits/stdc++.h>

using namespace std;

#define N 200010

#define M 500010

#define D 20

int n, q;

int l[N], r[N];

int f[M][D];

int work(int x, int y) {

	int ans = 0;

	for (int i = D - 1; i >= 0; --i) {

		if (f[x][i] < y) {

			x = f[x][i];

			ans |= (1 << i);

		}

	}

	x = f[x][0]; ++ans;

	if (x < y) ans = -1;

	return ans;

}

int main() {

	while (scanf("%d%d", &n, &q) != EOF) {

		for (int i = 1; i <= n; ++i) {

			scanf("%d%d", l + i, r + i);

			++l[i], ++r[i];

		}

		memset(f, 0, sizeof f);

		for (int i = 1; i <= n; ++i) {

			f[l[i]][0] = max(f[l[i]][0], r[i]);

		}

		for (int i = 1; i < M; ++i) {

			f[i][0] = max(f[i][0], max(i, f[i - 1][0]));

			for (int j = 1; j < D; ++j) {

				f[i][j] = max(f[i][j], max(f[i][j - 1], f[i - 1][j]));

			}

		}

		for (int j = 1; j < D; ++j) {

			for (int i = 1; i < M; ++i) {

				f[i][j] = max(f[i][j], f[f[i][j - 1]][j - 1]);

			}

		}

		int x, y;

		while (q--) {

			scanf("%d%d", &x, &y);

			++x, ++y;

			printf("%d\n", work(x, y));

		}

	}

	return 0;

}

巴特西

Codeforces 1175E Minimal Segment Cover

最新文章

热门文章