某岛

… : "…アッカリ~ン . .. . " .. .
April 3, 2020

区间 k 大值系列问题

基本功拙计啊。。。

序列

不考虑区间的话

静态

Hoare’s selection algorithm

动态

平衡树

区间询问的话

静态

POJ 2104. K-th Number
主席树。
莫队 + 平衡树。

单点修改

树状数组套主席树。
ZOJ 2112. Dynamic Rankings

区间修改

主席树不好打标记?
Luogu P4119 [Ynoi2018]未来日记

支持插入

替罪羊树套主席树。
“BZOJ3065”带插入区间K小值

综合练习

Liber OJ #106. 二逼平衡树

树上

BZOJ 1146. [CTSC2008]网络管理Network
紫荆花之恋

字符串

QSTRING
K-th good string

其它