首页 > 其他 > 详细

[Violet 6]蒲公英

时间:2019-01-21 22:07:21      阅读:193      评论:0      收藏:0      [点我收藏+]

传送门

这个题是我晚自习的时候看到的,那个时候觉得这个题好简单啊,一上手才发现这个题好难写啊,调了好久都没调对
算法是分块!!
很显然众数不能直接合并,那么我们可以考虑每个块上记录这个块的众数。
对于每个询问,它可能包含多个块,由于众数不好合并,所以我们需要记录任意两个块之间的众数,这个直接循环预处理就好了
很显然,对于每个询问区间\([L,R]\),它的众数只可能是它包含的块的众数和多出来的那两段的数
如何统计那两段多出来的数在这个区间出现的次数?
考虑将每个数的位置存入vector中,每次二分查找就行了。
记住离散化!

[Violet 6]蒲公英

原文:https://www.cnblogs.com/lcxer/p/10301232.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!