almost 3 years ago

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3065

分析:

首先膜一发出题的vfk。其次吐槽一下恶心的数据结构题。
这道题我写的是替罪羊套线段树,本想着做一道替罪羊的模板题,但是感觉我的心灵被深深的伤害了。。。
由于此题有插入操作,以至于我们无法用主席树等静态做法,只能用一棵平衡树来维护序列的顺序,然后平衡树上每一个点维护一棵权值线段树。
由于每个节点维护的是一棵线段树,所以如果有旋转的平衡树会相当的麻烦,因此引入了一个叫替罪羊树的东西。这种平衡树是不需要旋转的。(找vfk的论文看吧)
然后还有一个技术性问题就是如何使重建的复杂度降成,其实如果我们是动态开点的权值线段树完全不用担心这个问题,直接合并两个权值线段树就行。(找主席的论文看吧)
还有因为重建,要写个垃圾收集器,不然内存会起飞233(其实并不难写的说)
bzoj3065.cpp

← bzoj1069~1071:[SCOI2007]最大土地面积,修车,组队 NOIP2015总结 →
 
comments powered by Disqus