[LOJ#2732] 「JOISC 2016 Day 2」雇佣计划

参考博文

题目就是让我们求图中满足数值大于等于B的连通块数量

然后我们可以尝试转换为求连通块两端所产生的“谷”的数量,显然一个连通块对谷可以贡献2的答案,最终答案就是谷的数量除以2

(下图为查询$B_i$大小为4时的情况,每一个箭头代表一个谷)

[LOJ#2732] 「JOISC 2016 Day 2」雇佣计划

发现每两个数中间的空格都是有可能产生谷的,所以我们只需要维护有多少个空格满足产生谷的条件即可

记一个空格左边的数字为X,右边的数字为Y,当前询问为B,观察发现,当且仅当满足下列条件时,这个空格可以成为谷

$$min(X,Y)+1 \leq B \leq max(X,Y)$$

 

上一篇:痞子衡嵌入式:走进二维码(QR Code)的世界(1)- 引言


下一篇:【LOJ2838】「JOISC 2018 Day 3」比太郎的聚会(设阈值预处理/分块)