这应该是前天的
在整数域上的binary search 持续苦手
不过这题是有点更难了
照着答案写
==
应该没半天就忘了
一生就这样了
def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
# 找出 cnt以及sums of subarrays which summations are <= S
def cnt_sum_of_subs_less_than_or_equal_S(S):
count, total_sum, current_window_sum, running_sum = 0, 0, 0, 0
start = 0
for end, num in enumerate(nums):
running_sum += num * (end - start + 1)
current_window_sum += num
while current_window_sum > S:
running_sum -= current_window_sum
current_window_sum -= nums[start]
start += 1
count += end - start + 1
total_sum += running_sum
return count, total_sum
# 找出sum是前K小个的subarr
def SumofKSmallestSubarrays(K):
# Binary search, K is 1-index
l,r = 0, sum(nums)+1
while l<r:
mid = (l+r)//2
cnt, sum_of_arrays = cnt_sum_of_subs_less_than_or_equal_S(mid)
if cnt < K:
l=mid+1
else:
r=mid
cnt, sum_of_arrays = cnt_sum_of_subs_less_than_or_equal_S(l)
# binary seach找到的l只是: sum(sub)<=S的sub个数>=K里面的最小的S
# 但有可能有很多个subs的sum == S
# 所以这个cnt可能不是真的最小K个的sum
# 所以要另外减掉 (cnt-K)*S
# 若 cnt == K 则代表刚好只有一个subarr的sum==S
return sum_of_arrays - l*(cnt-K)
m = 10**9+7
ans = SumofKSmallestSubarrays(right)-SumofKSmallestSubarrays(left-1)
return ans % m