刷题记录:牛客NC53370 Forsaken的三维数点

传送门:牛客

题目描述:

Forsaken现在在一个三维空间中，空间中每个点都可以用(x,y,z)表示。突然，三维空间的主人出现
了，如果Forsaken想要继续在三维空间中呆下去，他就必须回答三维空间主人的问题.主人会在空间
中坐标为(x,y,z)处加一点能量值，当他加了一定的次数之后，他会问Forsaken一个问题：如果坐标
(0,0,0)为球心，那么至少需要多大的半径才能使得球内的能量值总和大于或者等于
k，在这里，半径为0也是可以的。这对于Forsaken来说实在是太难了，因此他把这个问题交给了你。
输入:
2
1 1 1 1
2 1
输出:
2

一道权值线段树的题目,并且需要快速查询前缀和是否满足要求

和这道题维护方法相同,同样有两种方法,甚至比那道题要简单,因为本题并没有区间修改操作,不需要$lazy$,所以具体如何使用线段树维护方法在这里就不再赘述了

对于本题来说,我们发现我们输出的半径必须为整数(md,刚开始我还在想如何维护double类型的呢),那么对于一个介于$a$和$b$的小数,显然只有当我们的半径为$b$的时候才能将这个数加入我们的计数当中,所以对于每一个距离,我们都进行向上取整即可

需要注意的是,因为有$0$的存在,这就需要我们对于每一个距离都加$1$,然后在最后得到半径的时候将半径-1输出即可

下面是具体的代码部分(用的是直接查询,不是二分):

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Segment_tree{int l,r,sum;
}tree[maxn*4];
int n;
void pushup(int rt) {tree[rt].sum=tree[ls].sum+tree[rs].sum;
}
void build(int l,int r,int rt) {tree[rt].l=l;tree[rt].r=r;if(l==r) {return;}int mid=(l+r)>>1;build(lson);build(rson);pushup(rt);
}
void update(int pos,int rt) {if(tree[rt].l==pos&&tree[rt].r==pos) {tree[rt].sum+=1;return ;}int mid=(tree[rt].l+tree[rt].r)>>1;if(pos<=mid) update(pos,ls);else update(pos,rs);pushup(rt);
}
int query(int l,int r,int rt,int k) {if(l==r) return l;int mid=(tree[rt].l+tree[rt].r)>>1;if(tree[ls].sum>=k) return query(l,mid,ls,k);else return query(mid+1,r,rs,k-tree[ls].sum);
}
int main() {n=read();build(1,180000,1);for(int i=1;i<=n;i++) {int opt=read();if(opt==1) {int x=read(),y=read(),z=read();double dist=__builtin_sqrt((double)x*x+(double)y*y+(double)z*z);int Dist=ceil(dist);update(Dist+1,1);}else {int k=read();if(tree[1].sum<k) {printf("-1\n");continue;}printf("%d\n",query(1,n,1,k)-1);}}return 0;
}