| 题目名称 | 265. 线段覆盖 |
|---|---|
| 输入输出 | xdfg.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 14 |
| 题目来源 |
 BYVoid
于2009-02-13加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：144， 提交：473， 通过率：30.44% | ||||
 +1s |
100 | 0.726 s | 18.98 MiB | C++ |
 青衫白叙 |
100 | 0.759 s | 15.95 MiB | C++ |
 PurpleWonder |
100 | 0.767 s | 7.92 MiB | C++ |
 AAAAAAAAAA |
100 | 0.778 s | 6.29 MiB | C++ |
 Fisher. |
100 | 0.811 s | 10.01 MiB | C++ |
 ┭┮﹏┭┮ |
100 | 0.863 s | 15.49 MiB | C++ |
 faraway |
100 | 0.902 s | 14.02 MiB | C++ |
 rewine |
100 | 0.922 s | 15.57 MiB | C++ |
 小DOTA |
100 | 0.933 s | 11.63 MiB | C++ |
|
Fisher. |
100 | 0.940 s | 15.57 MiB | C++ |
| 关于 线段覆盖 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
%%%%byvoid dalao
| ||||
|
查询可以O(1);
| ||||
|
| ||||
|
论超时的缘故____折腾人的快读。。。
| ||||
|
坑爹的内存限制。。第一次被卡MLE了！
| ||||
|
1AC 线段树
记录每一个节点的maxv,minv,leftc,rightc//leftc表示他最左边的端点被覆盖的次数，rightc表示最右边 如果这个节点的maxv是0那么说明这一段全是白的 如果这个节点的minv>0那么说明这一段全是黑的 一个节点的非连续节点数=LC的+RC的（如果LC最右边和RC最左边都不为0就-1） 难得线段树可以一次写对。。好感动TAT | ||||
|
发现Scanf与Cin的效率差太大
  超级傲娇的AC酱
2014-02-26 13:30
5楼
| ||||
|
| ||||
|
| ||||
|
..求解一个区间多层覆盖怎么记录...
 馒头
2013-10-18 08:51
2楼
| ||||
LOSER
Sky_miner
TA
HouJikan
rpCardinal
digital-T【问题描述】
有一根长度为 L 的白色条状物。有两种操作：
1.用一条长度为 T 的黑布盖住条状物的 [a, a+T] 这个区间 (0<=a, T<=L) 。
2.把某条黑布拿走。
输入 L 和 n 次操作，要你输出每次操作之后：
1.条状物上有多少个黑区间。
2.条状物上黑区间的总长度。
【输入格式】
输入文件第一行两个整数L(1<=L<=200000), n(1<=n<=200000)
以下有n行,第2--n+1行每行有3个整数m,a,T，m表示操作类型,1表示放入黑布,2表示拿走黑布,a,T表示黑布在L上的起始位置与长度,拿走的黑布保证是原来已经存在的.
【输出格式】
输出有n行,每行两个整数x,y,x表示L上的黑区间个数,y表示黑区间的总长度.
【输入样例】
20 4 1 5 3 1 7 2 2 5 3 1 16 3
【输出样例】
1 3 1 4 1 2 2 5