8
5
9
5
5
该题是二分法的应用。再用if进行选择就行了
以下为二分的基本模板
根据题目要求,查询数字x出现的最大下标,则find_upper_bound(q)-1为x出现的最后一个位置
查询代表查询数字x出现的最小下标,则find_upper_bound(q-1)为x出现的第一个位置
查询大于等于x且小于等于y的数字的个数,并保证x<=y,则需要y出现的最后一个位置减去x出现的第一个位置再+1
查询比x大且下标最小的数字的大小,则find_upper_bound(q)为大于x的第一个位置,这题要求的是数字,所以为a[find_upper_bound(q)]
代表查询比x小且下标最大的数字的大小,则find_upper_bound(q-1)-1为小于x的第一个位置,该题也要求是数字。
当find_upper_bound(q)==find_upper_bound(q-1)时 ,x不存在。
以上为该题题解。