二分
int pos=lower_bound(num,num+k,x) - num;
返回数组中第一个小于或等于被查数的值
int pos=upper_bound(num,num+k,x) - num;
返回数组中第一个小于被查数的值
int lb(int x)
{
int l=1,r=n+1;
while(l<r)
{
int mid=l+(r-l)/2;
if(sum[mid]>=x) r=mid;
else l=mid+1;
}
return l;
}
int lb(int x)
{
int l=1,r=n,mid;
while(l<=r)
{
mid=(l+r)/2;
if(a[mid]==x) break;
else if(a[mid]>x) r=mid;
else l=mid+1;
}
return a[mid];
}