因为写了下..顺便发上来吧..
外部线段树维护区间是可以的...
需要标记永久化
外部线段树每个节点上是2棵子线段树
一个是mark 一个是all
mark表示该区间每个点上都会加上mark线段树里的元素
all表示该区间所有点的元素集(我知道这回肯定会和谐)合
标记永久化 不用下传
插入的时候..首先维护all...然后如果覆盖整个区间就打标..
查询的时候首先弄出来所有相关的子线段树..扔到一个数组里面去..然后像带修改区间k大那样查询
发现不能直接用mark..因为mark是代表区间内所有点都加上这些元素..所以应该把mark乘上有效区间长度(就是自己区间和查询区间公共部分)
这样就可以查了..
本来以为写起来挺麻烦..结果意外的发现很简单...
内部线段树是单点插入..不用递归..
外部就当普通线段树写就行了...
貌似效率还不错...(BZOJ目前rank2 代码长度3KB....其中不少废话..)
fayaa.com/code/view/27526/
ps:这题如果把权值放外面据说很好写..我也不知道怎么样..反正这样确实挺好写的..
tag:BZOJ3110 zjoi K大数查询