【BZOJ3065】带插入区间K小值

听说这题做法特别多

写了个比较naive的,替罪羊树套主席树

替罪羊树上每个结点维护一棵主席树,维护该结点子树中数的出现情况,主席树动态开结点并回收删除结点节省空间。

为什么使用替罪羊树:因为替罪羊树不需要旋转。每次旋转会导致主席树中子树大小个结点的变化,复杂度过高。

暴力重建将所有主席树清空重建即可。

说点什么

  Subscribe  
提醒