Codeforces 1354 D. Multiset（树状数组）

题意;

要你实现一个求第k大数的数据结构。
树状数组模板题。

AC代码：

const int N = 1e6 + 50;
int a[N];
int n, q;
void add(int p, int val)
{
  while (p <= n)
  {
    a[p] += val;
    p += lowbit(p);
  }
}

int query(int p)
{
  int res = 0, cnt = 0;
  per(i, 20, 0)
  {
    if (res + (1 << i) <= n && cnt + a[res + (1 << i)] < p)
    {
      cnt += a[res + (1 << i)];
      res += (1 << i);
    }
  }
  return res + 1;
}

int main()
{
  sdd(n, q);
  rep(i, 1, n)
  {
    int val;
    sd(val);
    add(val, 1);
  }
  int cnt = n;
  while (q--)
  {
    int val;
    sd(val);
    if (val > 0)
    {
      add(val, 1);
      cnt++;
    }
    else
    {
      add(query(-val), -1);
      cnt--;
    }
  }
  if (!cnt)
    puts("0");
  else
    pd(query(1));
  return 0;
}