111qqz的小窝

老年咸鱼冲锋!

hdu 1556Color the ball (树状数组,更新区间,查询单点)

这道题和之前做的树状数组略有不同。
以前的都是更新单点,查询区间,这次反了过来。
做法差不多。
如果更新区间【x,y】增加1
那么只要 update (x,1),update (y+1,-1)
问单点的时候,sum(i)就是i点的值,而不是1..i的和。
可以看做告诉公路收费口的比喻,update (x,1)相当于入口
update (y+1,-1)相当于出口。
而sum(i)就相当于被几个告诉公路穿过,或者说i点属于几个高速公路,所以是求和
还记得noip2012的时候在tyvj上遇到了一道线段数的题,被@Ocean 海洋兄用了一个高速公路的神奇比喻解法A掉了。
现在回想,原来是用了树状数组。

说点什么

您将是第一位评论人!

提醒
wpDiscuz
粤ICP备18103363