Description
很不幸,蔡老师最后还是鸽了。愤怒的网友们冲进了蔡老师的家里,蔡老师不得不向网友们道歉。
n个网友的愤怒值为f1,f2,…,fn当蔡老师向第i个网友道j次歉,第i网友的愤怒值会变成⌊fi/2^j⌋。蔡老师希望一共道歉k次使得网友们的愤怒值之和最小。
蔡老师希望你能回答,对于[l,r]这一段网友fl,fl+1,…,fr,道歉一共k次,这些网友们的愤怒值之和最小是多少。
Solution
k次道歉贪心地想一定是要道贡献最大的k次歉的,所以可以对所有fi对于道不同的歉构建主席树,查询前k大的贡献就可以了
而一个针对时间和空间的优化是,我们把值域分块,算出道歉i次在不同值域中的贡献,我们便可以优化从查询k变成查询k剔除了包含块的p,而进入主席树的次数也因此减少了
Code
1 |
|