1. 首页
  2. 线段树

Poj 2528 Mayor's posters (成段更新+离散化)

题意:在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报
线段树功能:update:成段替换 query:简单 hash
思路:这题数据范围很大,直接搞超时+超内存,需要离散化:
离散化简单的来说就是只取我们需要的值来用,比如说区间[1000,2000],[1990,2012]
我们用不到[-∞,999][1001,1989][1991,1999][2001,2011][2013,+∞]这些值,所以我
只需要 1000,1990,2000,2012 就够了,将其分别映射到 0,1,2,3,在于复杂度就大大的
降下来了
所以离散化要保存所有需要用到的值,排序后,分别映射到 1~n,这样复杂度就会小
很多很多
1~10  1~4  6~10
对于这种案例,如果直接离散化X[1]=1,X[2]=4,X[3]=6,X[4]=10
计算的结果就会出现错误~
为了解决这种缺陷,我们可以在排序后的数组上加些处理,比如说[1,2,6,10]
如果相邻数字间距大于 1 的话,在其中加上任意一个数字,比如加成[1,2,3,6,7,10],然
后再做线段树就好了.

 

评分 0, 满分 5 星
0
0
看完收藏一下,下次也能找得到
  • 版权声明:本文基于《知识共享署名-相同方式共享 3.0 中国大陆许可协议》发布,转载请遵循本协议
  • 文章链接:http://www.carlstedt.cn/archives/1105 (转载时请注明本文出处及文章链接)
上一篇:
:下一篇

发表评论

gravatar

快来吐槽一下吧!

  1. .01 4:06
  2. .02 1:47
  3. .03 3:39
  4. .04 1:40