题目大意
??模拟一下multiset，一共有两个操作:
??1.插入一个数
??2.删除第k小的数
解题思路
??用权值树状数组来维护，主要是新学了树状数组倍增的方法，可以比二分少一个log来查找第k小的数，需要maxn是2的幂。
??比如要查找第k小的数，我们倒着枚举二进制位，如果区间\([0, 2^x]\)的数的数量比k要小，那么说明第k小的数肯定是比\(2^x\)要大的，那么根据二进制的性质，这个数肯定是介于\([2^x, 2^{x+1}]\)之间的，那么我们就用一个变量res加上\(2^x\)，然后k减去其中的数量。再继续枚举更低位，判断区间\([res, res+2^y]\)的数是否比k大，来继续更新res和k的值，这样可以再复杂度为log(n)的情况下找出第k小数。
const int maxn = 1<<20;
const int maxm = 2e5+10;
int n, q, c[maxn+1];
void add(int x, int y) {
while(x<maxn) {
c[x] += y;
x += x&-x;
}
}
int get_k(int x) {
int res = 0;
for (int i = maxn/2; i>=1; i>>=1)
if (c[res+i]<x) {
res += i;
x -= c[res];
}
return res+1;
}
int main(void) {
IOS;
cin >> n >> q;
for (int i = 1; i<=n; ++i) {
int num; cin >> num;
add(num, 1);
}
while(q--) {
int num; cin >> num;
if (num>0) add(num, 1);
else {
num = -num;
int x = get_k(num);
add(x, -1);
}
}
int ans = 0;
for (int i = 1; i<maxn; ++i)
if (c[i]) {
ans = i;
break;
}
cout << ans << endl;
return 0;
}