HDU 4614 – Vases and Flowers

题目链接:HDU – 4614

题意:Alice有N个花瓶(标号为0到N-1)。当她收到一些花时,她会随机的选择一个瓶子A,从它开始遍历$A, A+1,A+2 \cdots N-1$号瓶子,遇到空瓶子就放一朵花进去,直到花朵放完或没有瓶子,剩下的花将被丢弃。有时,她也会清理标号从A到B的花瓶($A \leq B$)。花瓶里的花会被丢弃。每次插入花的时候输出插花的第一个瓶子和最后一个瓶子,删除的时候输出一共删了多少朵花。

考虑线段树做区间覆盖操作,维护区间和。当前位置能插花记为1,不能插花记录为0。$[0,N-1]$映射到$[1,N]$方便建立线段树。

一个点的后面能否插入花取决于这个点的后缀和是否为0。如果能插花,就对这个后缀区间进行二分,在$[x,N]$找到第一个前缀和为1的位置作为起点,找到第一个前缀和为$f$的位置作为终点,如果不存在前缀和为$f$的位置则$x$后有几个可行位置(为1的位置)就插几朵花。输出这两个点后这两个点内的区间。

删除操作即查询区间和,用区间长度减去区间和得到已经插花的位置的总数。

这里要注意如果将已经插花设为1,没有插花设为0,是不方便二分的。

 

说点什么

avatar
50
  Subscribe  
提醒