NC 53370 BIT

题意

传送门 NC 53370

题解

以半径的顶函数为索引，用 $BIT$ 维护球体内的能量点数；用类似二分的方法，从高位向低位比特枚举至少有 $k$ 点能量对应的半径包含的区间，求解之。

#include <bits/stdc++.h> using namespace std; #define maxn 200000 int n, bit[maxn + 1]; void add(int i, int x) { while (i <= maxn) { bit[i] += x; i += i & -i; } } int seeksum(int x) { int res = 0, sum = 0; for (int i = 17; i >= 0; i--) { res += 1 << i; if (res > maxn || sum + bit[res] >= x) { res -= 1 << i; } else { sum += bit[res]; } } return res + 1; } int main() { scanf("%d", &n); while (n--) { int op; scanf("%d", &op); if (op == 1) { double x, y, z; scanf("%lf%lf%lf", &x, &y, &z); int r = ceil(sqrt(x * x + y * y + z * z)); add(r + 1, 1); } else { int k; scanf("%d", &k); int r = seeksum(k); printf("%d\n", r >= maxn ? -1 : r - 1); } } return 0; }