POJ 2528 – Mayor’s posters

题面链接:POJ – 2528

题意:$N(1 \leq N \leq 10^4)$个人贴海报,每张海报的左右端点$1 \leq l_i, r_i \leq 10^7$,求出最后还能看见多少张海报。

这$N$张海报是按顺序贴的,那么越往后贴的一定在最上面。我们可以先记录下贴海报的顺序,然后从最后一张往前扫一遍。如果当前第$i$个海报的区间$[l_i, r_i]$内有没有被贴的空间,那么这个海报就可以被看到。

由此我们把这个问题转化为了一个区间覆盖问题,考虑线段树,我们可以用0和1来表示每个点的状态,维护区间最小值,如果区间最小值为0则说明这个区间有未被贴的空间,如果最小值为1(即全1)则说明这个区间没有空位了,$10^7$级别需要离散化。离散化时应注意如果存在点$x$和$y$并且$y-x>1$,那么要再加一个点$x+1$进离散化点集中,原因是例如$[1, 10], [1, 5], [8, 10]$的区间按照简单的方法离散化之后$[1,5]$和$[8,10]$会覆盖$[1,10]$,实际上中间还有$[6,7]$的可行空间。

有几个注意点:

  1. 离散化尽量使用sort + unique的方法,使用set + map时间常数比较大。
  2. 线段树数组和lazy-tag数组可以使用bool类型存,memset的时候节省时间。
  3. 最多是40000个点,不是20000个。
  4. 数据比较弱,离散化错误也能过。

 

说点什么

avatar
50
  Subscribe  
提醒