CF1175E Minimal Segment Cover

水深无声 2021-12-20 10:29 158阅读 0赞

[CF1175E Minimal Segment Cover][]

> 给定 \\(n\\) 条形如 \\(\[l,\\ r\]\\) 的线段，有 \\(m\\) 次询问，求 \\(\[x,\\ y\]\\) 最少要用多少条线段才能被完全覆盖，无解输出 \\(-1\\)
> 
> \\(n,\\ m\\leq2\\times10^5,\\ l,\\ r,\\ x,\\ y\\in\[0,\\ 5\\times10^5\]\\)

倍增

--------------------

首先，有一个 \\(O(nm)\\) 的贪心，每次选择左端点不大于 \\(x\\) ，右端点最大的线段，并更新 \\(x\\) 为右端点，直到 \\(x>y\\)

可以用倍增优化，令 \\(p\_\{i,\\ j\}\\) 表示左端点为 \\(j\\) ，选择 \\(2^i\\) 条线段所能得到的右端点最大值。预处理了这个玩意儿就可以 \\(O((n+m+a\_i)\\log a\_i)\\) 做了

处理出 \\(i\\in\[0,\\ \\log n\],\\ j\\in\[0,\\ 5\\times10^5\]\\) 的 \\(p\_\{i,\\ j\}\\) ，可以有效地避免一些边界判断，无解即为 \\(ans>n\\)

时间复杂度 \\(O((n+m+a\_i)\\log a\_i)\\) ，空间复杂度 \\(O(a\_i\\log a\_i)\\)

代码

#include <bits/stdc++.h> using namespace std; const int maxn = 5e5 + 10; int n, m, pos[19][maxn]; inline void chkmax(int &x, int y) { if (x < y) x = y; } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { int x, y; scanf("%d %d", &x, &y); chkmax(pos[0][x], y); } for (int i = 1; i < 500001; i++) { chkmax(pos[0][i], pos[0][i - 1]); } for (int i = 1; i < 19; i++) { for (int j = 0; j < 500001; j++) { pos[i][j] = pos[i - 1][pos[i - 1][j]]; } } while (m--) { int l, r, ans = 0; scanf("%d %d", &l, &r); for (int i = 18; ~i; i--) { if (pos[i][l] < r) { ans |= 1 << i, l = pos[i][l]; } } printf("%d\n", ans < n ? ans + 1 : -1); } return 0; }

转载于:https://www.cnblogs.com/Juanzhang/p/10999555.html

[CF1175E Minimal Segment Cover]: http://codeforces.com/problemset/problem/1175/E

发表评论取消回复

表情：

评论列表（有 0 条评论，158人围观）

还没有评论，来说两句吧...

相关阅读

相关【贪心】CF1822 E

[Problem - 1822E - Codeforces][] 题意： ![2e9c008736434bd3aade35f13ba3671b.png][] ![e793

女爷i/ 2024年03月23日 23:48/ 0 赞/ 72 阅读

相关【构造】CF1734 E

[Problem - 1734E - Codeforces][] 题意： ![434e61d374814555abe1a965962475f0.png][] 思路： !

超、凢脫俗/ 2024年03月23日 22:45/ 0 赞/ 58 阅读

相关构造——cf1214E

首先定义三元组（2\i-1,2\i,d），将n个三元组按d降序排列，然后取每个三元组的2\i-1连在一起，构成一条长为n-1的链然后降序枚举每个三元组，把对应的2\i在链上

深藏阁楼爱情的钟/ 2023年10月11日 09:04/ 0 赞/ 11 阅读

相关 CF891E Lust

CF891E Lust -------------------- 鸽子更博了 Orz Itst 神仙结论：最后的答案是一开始的\\(\\prod a\_i\\)减去

迈不过友情╰/ 2023年08月17日 17:29/ 0 赞/ 118 阅读

相关 Educational Codeforces Round 66 (Rated for Div. 2) Minimal Segment Cover

题意：给你n个区间，m个询问，对于每个询问求最少可以用多少个区间完成覆盖，区间可以重叠。思路：倍增法，f\[i\]\[j\]表示i点连续向后扩展2^j个区间后可以达到的

落日映苍穹つ/ 2022年01月22日 11:49/ 0 赞/ 182 阅读

相关 [CF1111E]Tree

题目大意：给一棵$n(n\\leqslant10^5)$个点的树，有$q(q\\leqslant10^5)$次询问，每次询问给出$k,m,r$表示把以下$k$个点分成不超过$m

素颜马尾好姑娘i/ 2021年12月22日 04:15/ 0 赞/ 211 阅读

相关 CF1156E Special Segments of Permutation

[CF1156E Special Segments of Permutation][] > 给定一个长度为 \\(n\\) 的排列，求有多少个区间 \\(\[l,\\ r\]

爱被打了一巴掌/ 2021年12月20日 10:29/ 0 赞/ 176 阅读

相关 CF1175E Minimal Segment Cover

[CF1175E Minimal Segment Cover][] > 给定 \\(n\\) 条形如 \\(\[l,\\ r\]\\) 的线段，有 \\(m\\) 次询问，求

水深无声/ 2021年12月20日 10:29/ 0 赞/ 159 阅读

相关 CF 166E Tetrahedron

E. Tetrahedron time limit per test 2 seconds memory limit per test 256 megabytes in

蔚落/ 2021年12月19日 14:35/ 0 赞/ 209 阅读

相关 cf 1009E

如何看待某cf2000分选手不会一道tag1900的题？难。考虑每段距离的贡献， a\[i\]出现在位置j上，当且仅当j-i休息，并且中间的都不是休息的。

曾经终败给现在/ 2021年10月25日 12:56/ 0 赞/ 265 阅读