JZOJ | NOIP2018模拟10.27 百鸽笼

把序列倒过来建主席树

没了。

 

闲的无聊随便写点| [CQOI2015]任务查询系统

主席树板儿

考虑把添加优先级为 k 的任务转化为在时间 \mathrm{st} 上加 k ,在时间 \mathrm{en}+1 上减 k

那么这样就成功维护了差分咯,然后每棵权值树单独地维护前缀和就行。

注意要离散化和排序。

06/06,应该是一轮集训 (之前) 做的题咯。

POI2008 Building blocks

主席树题。

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

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

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

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

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

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