首页 > 其他 > 详细

51nod 1533 && CF538F

时间:2017-01-28 21:10:04      阅读:329      评论:0      收藏:0      [点我收藏+]

题目:难以简述,请传送门

神犇题解Ⅰ   神犇题解Ⅱ

好劲啊跪在地上。。完全没接触过K叉树的性质。。

对于每个询问,我们并不关心叶节点,只关心其他的节点。而一个完整K叉树的内节点个数是O(n/k)的,所以总计下来就是调和级数,也就是O(nlogn)个点需要我们计算。

然后对于每个点我们要查询一个区间内有多少个点权值小于它,并累计入答案。我们可以用两种方式在O(logn)时间复杂度实现这个操作

1.树状数组。我们将每个询问区间拆成[1,l-1],[1,r],然后减掉就好了。具体来说,我们把区间排序,然后依次用树状数组处理,一边计算贡献一边更新树状数组(操作过程类似于求逆序对)。

2.主席树。这个不用多赘述。

总复杂度O(nlognlogn)。

51nod 1533 && CF538F

原文:http://www.cnblogs.com/enigma-aw/p/6354496.html

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