https://ac.nowcoder.com/acm/contest/1221/G
题解：树状数组解决下标I以前有多少小于/大于他的数
对应到这道题就是说二分半径，每次加入点时都按照与圆心的距离（半径）加入树状数组，利用树状数组前缀和的性质求
细节：这道题有半径为0的情况，而树状数组下标从1开始的，记得特判一下
#include <bits/stdc++.h> #define ll long long using namespace std; const int maxn = 1e6 + 5; const int INF = 0x3f3f3f3f; const ll MOD = 1e9 + 7; int c[maxn]; int zero=0; int lowbit(int x){ return x&(-x); } void add(int id,int p){ while(id<=300005){ c[id]+=p; id+=lowbit(id); } } int sum(int id){ int ans=0; while(id>=1){ ans+=c[id]; id-=lowbit(id); } return ans; } int len(ll x,ll y,ll z){ return ceil(sqrt(x*x+y*y+z*z)); } bool check(int x,int k){ if(x==0){ if(zero>=k) return 1; else return 0; } int p=sum(x); //cout<<x<<" "<<p<<endl; if(p>=k) return 1; else return 0; } int main(){ int q; cin>>q; int mx=0; while(q--){ int op; cin>>op; if(op==1){ ll x,y,z; cin>>x>>y>>z; int p=len(x,y,z); if(p==0) zero++; else add(p,1); mx=max(mx,p); } else{ int k; cin>>k; int l=0; int r=mx+1; int ans=-1; while(l<=r){ int mid=(l+r)/2; if(check(mid,k)){ ans=mid; r=mid-1; }else{ l=mid+1; } } cout<<ans<<endl; } } return 0; }
