这个是一个简单题，不过因为想到比标程时间复杂度更低的方法就尝试了一下。
思路：虽然加点是三维数点，但是我们要求的是半径的大小，这样的话，就可以转变为一维的问题。
标程的解法是，用树状数组维护，然后二分答案，这样的话，时间复杂度就是O(n*logn*logn).
但是，可以建立权值线段树，在树上跑的时候，就可以二分出答案了。
如果左节点的个数不够的话，那么肯定要跑到右节点，这样不断二分，最终的边界就是我们要求的答案了,复杂度为 O(nlogn)。
之所以能想到是因为之前有过类似题 ——> 传送门.
//#pragma comment(linker, "/STACK:1024000000,1024000000") //#pragma GCC optimize(2) #include <bits/stdc++.h> using namespace std; typedef double dou; typedef long long ll; typedef pair<int, int> pii; typedef map<int, int> mii; #define pai acos(-1.0) #define M 200005 #define inf 0x3f3f3f3f #define mod 1000000007 #define IN inline #define W(a) while(a) #define lowbit(a) a&(-a) #define left k<<1 #define right k<<1|1 #define lson L, mid, left #define rson mid + 1, R, right #define ms(a,b) memset(a,b,sizeof(a)) #define Abs(a) (a ^ (a >> 31)) - (a >> 31) #define random(a,b) (rand()%(b+1-a)+a) #define false_stdio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) int tree[M<<2]; int n = 175000, Q, len; dou x, y, z; void Updata(int L, int R, int k,int pos) { if (L == R) { tree[k]++; return; } int mid = L + R >> 1; if (pos <= mid)Updata(lson, pos); else Updata(rson, pos); tree[k] = tree[left] + tree[right]; } void Query(int L, int R, int k,int aim) { if (L == R) { cout << (tree[k] >= aim ? L : -1) << endl; return; } int Lsum = tree[left]; int mid = L + R >> 1; if (Lsum >= aim)Query(lson, aim); else Query(rson, aim - Lsum); } int main() { false_stdio; cin >> Q; for (int i = 1,opt; i <= Q; i++) { cin >> opt; if (opt == 1) { cin >> x >> y >> z; len = ceil(sqrt(x * x + y * y + z * z)); Updata(0, n, 1, len); } else { cin >> len; Query(0, n, 1, len); } } return 0; }