Questions
Medium
Hard
Solutions
Medium
class NumArray:
def __init__(self, nums: List[int]):
self.nums = [0] + nums
self.BIT = self.nums[:]
for i in range(1, len(self.BIT)):
if (j := i + (i & -i)) < len(self.BIT):
self.BIT[j] += self.BIT[i]
def update(self, index: int, val: int) -> None:
index += 1
delta = val - self.nums[index]
self.nums[index] = val
while index < len(self.BIT):
self.BIT[index] += delta
index += (index & -index)
def sumRange(self, left: int, right: int) -> int:
return self.prefixSum(right) - self.prefixSum(left - 1)
def prefixSum(self, index: int) -> int:
index += 1
total = 0
while index > 0:
total += self.BIT[index]
index -= (index & -index)
return total
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(index,val)
# param_2 = obj.sumRange(left,right)
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
def update(i: int, val: int):
i += 1
while i <= n:
BIT[i] += val
i += i & -i
def presum(i: int) -> int:
i += 1
total = 0
while i > 0:
total += BIT[i]
i -= i & -i
return total
people.sort(key=lambda p: (p[0], -p[1]))
n = len(people)
BIT = [0] * (n + 1)
for i in range(1, n):
i += 1
BIT[i] += 1
if (j := i + (i & -i)) <= n:
BIT[j] += BIT[i]
result = [None] * n
for p in people:
left, right = 0, n
while left < right:
mid = left + (right - left) // 2
if presum(mid) < p[1]:
left = mid + 1
else:
right = mid
result[left] = p
update(left, -1)
return result
class Solution:
def numTeams(self, rating: List[int]) -> int:
ans = 0
for i, ri in enumerate(rating):
large_before, small_before = 0, 0
large_after, small_after = 0, 0
for j, rj in enumerate(rating):
if j < i:
if rj < ri:
small_before += 1
else:
large_before += 1
elif i < j:
if ri < rj:
large_after += 1
else:
small_after += 1
ans += small_before * large_after
ans += large_before * small_after
return ans