求助:线段树二分
  • 板块学术版
  • 楼主HY248
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/9/23 20:17
  • 上次更新2023/11/2 18:27:08
查看原帖
求助:线段树二分
383638
HY248楼主2023/9/23 20:17

求助:这样写线段树二分,复杂度是严格 loglog 的吗 qwqqwq

还有,是不是把前两行改成

if(l==r){
	if(a[p].min>s) return -1;
	else return l;
}

复杂度就会有问题

task:task: 找到位置 >=x>=x 的第一个值 <=s<=s 的位置

int query(int p,int l,int r,int x,ll s){
	if(a[p].min>s) return -1; 
	if(l==r) return l;
	int mid=(l+r)/2;
	if(x<=mid){
		int res=query(p*2,l,mid,x,s);
		if(res!=-1) return res;
		else return query(p*2+1,mid+1,r,x,s);
	}
	else return query(p*2+1,mid+1,r,x,s);
}
2023/9/23 20:17
加载中...