POJ 2528 – Mayor's posters

这$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. 数据比较弱，离散化错误也能过。