BZOJ 4631 踩气球

发布于 2017-10-19  126 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4631

题意:单点减一,强制在线询问在给定区间内有多少个区间已经为空了。


用一个线段树维护整个序列,每次单点减一是容易的。用这个线段树去把每个熊孩子的区间拆开,在对应节点像打标记那样存储。

如果一个区间和被减到 0,则这个区间对应的熊孩子区间可能被更新答案,用一个桶记录每个熊孩子被拆出的多个区间还有几个不为 0 的。

具体存储的过程可以对每个节点开一个 vector-_-,然后就可以了。

 


一个非常弱的准退役OIER