HDU 2852 (树状数组+无序第K小)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2852
题目大意：操作①：往盒子里放一个数。操作②：从盒子里扔掉一个数。操作③：查询盒子里大于a的第K小数。
解题思路：
由于模型是盒子，而不是序列，所以可以用树状数组的顺序维护+逆序数思想。
对应的树状数组Solution：
放一个数
$Add(val,1)$
类似维护逆序数的方法，对应位置上计数+1。
删一个数
判断：$getSum(val)-getSum(val-1)=0$
可以Hash处理，但是没有必要。如果没有val这个数，那么$getSum(val)=getSum(val-1)$是必然的。
删除：$Add(val,-1)$
即加上-1，撤销之前的操作。
查询
查询比较麻烦。
首先要判断$getSum(maxn)-getSum(val)>=k$
然后，将查询大于a的第K小数转化为大于1的第X+K小数。
其中$X=getSum(val)$。然后，对区间$[1,maxn]$进行二分。
二分处理手段比较特殊，主要是由于有重复的数，所以直接找出$\arg \min \limits_{mid} getSum(mid)=X+K$是不行的。
$getSum(mid)=X+K$有时候并不能二分找到。
解决方法是：
$\left\{\begin{matrix}
R=mid \quad (getSum(mid)<=X+K)\\
\\
L=mid \quad (other)
\end{matrix}\right.$
$ans=R$
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
