传送门
题意： 现有一个多元集合，你有如下两种操作：
- 将数k加入多元集合中
- 找到多元集合升序第k位，并将其删除
最后打印出集合中的任意元素，若集合为空直接输出0。
思路：
- 利用树状数组统计数值下标的个数，
- 通过树状数组的前缀和性质再使用二分锁定第k个数的位置。
代码实现：
#include<bits/stdc++.h>
#define lowbit(x) (x &(-x))
using namespace std;
const int N = 1e6 + 500;
int n, q, x, tr[N];void add(int k, int d)
{
while(k < N){
tr[k] += d;k += lowbit(k);}
}int ask(int x)
{
int sum = 0;while(x){
sum += tr[x];x -= lowbit(x);}return sum;
}int Find(int x,int k) {
int l = x + 1, r = N, ans = -1;while(l <= r) {
int mid = (l + r) >> 1;if(ask(mid) - ask(x) >= k) r = mid - 1, ans = mid;else l = mid + 1;}return ans;
}signed main()
{
scanf("%d%d", &n, &q);for(int i = 1; i <= n; i ++) {
scanf("%d", &x);x += 100;add(x, 1);}while(q --){
scanf("%d", &x);if(x <= 0){
x = -x;int tmp = Find(1,x);if(tmp == -1) continue;add(tmp, -1);}else add(x + 100, 1);}int ok = 1;//如果集合还存在元素就输出第一个元素for(int i = 1; i <= n; i ++) {
if(ask(i + 100) - ask(i + 99)) {
printf("%d\n", i);ok = 0;break;}}if(ok) printf("0\n");return 0;
}