链接：https://ac.nowcoder.com/acm/problem/53370
来源：牛客网
题目描述
Forsaken现在在一个三维空间中，空间中每个点都可以用(x,y,z)(x,y,z)(x,y,z)表示。突然，三维空间的主人出现了，如果Forsaken想要继续在三维空间中呆下去，他就必须回答三维空间主人的问题。
主人会在空间中坐标为(x,y,z)(x,y,z)(x,y,z)处加一点能量值，当他加了一定的次数之后，他会问Forsaken一个问题：如果坐标(0,0,0)(0,0,0)(0,0,0)为球心，那么至少需要多大的半径才能使得球内的能量值总和大于或者等于kkk，在这里，半径为000也是可以的。这对于Forsaken来说实在是太难了，因此他把这个问题交给了你。
输入描述:
第一行一个nnn表示操作的次数。
接下来每行首先一个整数opopop表示操作的种类。
如果op=1op = 1op=1，接下来333个整数x,y,zx,y,zx,y,z表示能量值增加的坐标。
如果op=2op =2op=2，接下来一个整数kkk表示要求的能量值总和。
输出描述:
对于每个op=2op=2op=2的操作，输出一个整数表示球的半径。(数据保证至少有一个222操作)
如果没有满足答案的半径，输出−1-1−1。
思路
题目要求是求空间内球体的半径多长时可以符合能量值大于等于k的情况，这个时候由于输出的是一个整数，也就是这个整数是来表示半径的。
再加上题目求的是区间和，所以考虑树状数组。
接下来为了使能够构成树状数组，在半径可以回答0的情况时是无法构成树状数组的，因为树状数组是到达1处时求和就结束的。
所以我们给求出的每个半径都+1就可以构成树状数组了。
然后二分判断情况。
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl '
'
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(case,x); cout<<case<<" : "<<x<<endl;
#define open freopen("ii.txt","r",stdin)
#define close freopen("oo.txt","w",stdout)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
using namespace std;
#define int long long
const int maxn=1e6+10;
int k;
int d[maxn];
inline int lowbit(int x){return -x&x;}
void add(int x,int y){
while(x<=200000){
d[x]+=y;x+=lowbit(x);
}
}
int get_sum(int x){
int ans=0;
while(x){
ans+=d[x];x-=lowbit(x);
}
return ans;
}
signed main(){
int m;
cin>>m;
while(m--){
int x,y,z,op;
cin>>op;
if(op==1){
cin>>x>>y>>z;
add(ceil(sqrt(x*x+y*y+z*z))+1,1);
}else{
cin>>k;
if(get_sum(200000)<k){
cout<<-1<<endl;
}else{
int l=1,r=200000,mid;
while(l<=r){
mid=l+r>>1;
if(get_sum(mid)>=k){
r=mid-1;
}else l=mid+1;
}
cout<<r<<endl;
}
}
}
}