BZOJ 4631 踩气球


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

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


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

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

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

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 4631 踩气球


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: ,