首页
注册
登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请
登录
V2EX 提问指南
广告
V2EX
›
问与答
请教一个数据结构问题, @acmers
polythene
·
2013-05-29 01:08:03 +08:00
· 2341 次点击
这是一个创建于 4036 天前的主题,其中的信息可能已经有所发展或是发生改变。
我把问题抽象了下:
给定一个大区间,比方说[0, 2147483648],现给如下子区间涂色:
[0, 500]
[501, 700]
[1000, 1500]
...
请问到最后未着色的区间有哪些?
题目的一些限制,
1、 区间很大,正常的内存无法存储
2、被涂色的区间相对较多,即未被涂色的区间只占少数
不知道各位高人有没有什么好的解决方法,先谢了。。
涂色
区间
现给
3 条回复
•
1970-01-01 08:00:00 +08:00
1
hadoop
2013-05-29 01:12:28 +08:00 via Android
1
不出意外请放狗搜线段树
2
Gestalt
2013-05-29 01:14:41 +08:00
1
子区间在10^5内线段树离散化……大概如此了。
好久没做题具体怎么写忘了.讲离散化的文很多的……
3
polythene
OP
2013-05-29 01:26:07 +08:00
@
hadoop
@
Gestalt
不出意外线段树果然出来了,我上来求问主要是不知道有没有更高效的数据结构了,因为印象中线段树也是个内存大户,而以前做题时要先离散的情况我从没写对过,现在形成心理阴影了,或许以前我的理解太浅薄~~
感谢回复!
关于
·
帮助文档
·
博客
·
API
·
FAQ
·
实用小工具
·
984 人在线
最高记录 6679
·
Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.5 · 29ms ·
UTC 22:52
·
PVG 06:52
·
LAX 15:52
·
JFK 18:52
Developed with
CodeLauncher
♥ Do have faith in what you're doing.