POI2008 Building blocks

主席树题。

首先我们考虑,这个问题就是区间上的中点问题。

\mathrm{cost} = \sum | \overline{x} - a_i |

然后事情就变得很简单了。

权值主席树 -> 区间第 \mathrm{k} 大可以求得中点。

注意考虑区间长度是偶数的问题。。这个我们去取平均值就好了。

求出来位置之后我们在主席树上走一遍,对于不包含中点的区间我们直接可以算出贡献,包含的递归进去算就好了。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据