查询第一个小于等于k值的节点下标时,不要把二分写成这样子:
inline int query1(int l,int r,int k)
{
int mid = 0;
while(l < r)
{
mid = (l + r) >> 1;
if(a[mid] <= k) l = mid + 1;
else r = mid - 1;
}
return min(n,l);
}
要写成这样子:
inline int query1(int l,int r,int k)
{
int mid = 0,ans = l;
while(l < r)
{
mid = (l + r) >> 1;
if(a[mid] <= k)
{
ans = l;
l = mid + 1;
}
else r = mid - 1;
}
return min(n,ans);
}