题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2852
题目大意：操作①：往盒子里放一个数。操作②：从盒子里扔掉一个数。操作③：查询盒子里大于a的第K小数。
解题思路：
由于模型是盒子，而不是序列，所以可以用树状数组的顺序维护+逆序数思想。
对应的树状数组Solution：
放一个数
$Add(val,1)$
类似维护逆序数的方法，对应位置上计数+1。
注意Add的while范围要写成$while(x<maxn)$
如果范围不是最大，那么会导致某些sum[x]不会被更新。
删一个数
判断：$getSum(val)-getSum(val-1)=0$
可以Hash处理，但是没有必要。如果没有val这个数，那么$getSum(val)=getSum(val-1)$是必然的。
删除：$Add(val,-1)$
即加上-1，撤销之前的操作。
查询
查询比较麻烦。
首先要判断$getSum(maxn-1)-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.$
这样，如果没有二分到，会最近的最小R作为结果。
$ans=R$
代码
#include "cstdio"
#include "map"
#include "cstring"
#include "algorithm"
using namespace std;
#define LL long long
#define maxn 100005
LL sum[maxn];
int val,n,kth,cmd;
int lowbit(int x) {return x&(-x);}
LL getSum(int x)
{
LL ret=;
while(x>)
{
ret+=sum[x];
x-=lowbit(x);
}
return ret;
}
void update(int x,int s)
{
while(x<maxn)
{
sum[x]+=s;
x+=lowbit(x);
}
}
LL query(int a,int k)
{
LL low=getSum(a),res;
low+=k;
int l=,r=maxn-,m;
while(l<r-)
{
m=l+(r-l)/;
res=getSum(m);
if(res>=low) r=m;
else l=m;
}
return r;
}
int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d",&n)!=EOF)
{
memset(sum,,sizeof(sum));
for(int i=;i<=n;i++)
{
scanf("%d",&cmd);
if(cmd==)
{
scanf("%d",&val);
update(val,);
}
else if(cmd==)
{
scanf("%d",&val);
LL key=getSum(val)-getSum(val-);
if(key==) printf("No Elment!\n");
else update(val,-);
}
else
{
scanf("%d%d",&val,&kth);
if(getSum(maxn-)-getSum(val)<kth) printf("Not Find!\n");
else
{
LL ans=query(val,kth);
printf("%I64d\n",ans);
}
}
}
}
}