혼자 풀어본 느린 O(nlogn) 솔루션


class Solution:
def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
m,M,ob = [],[],[]
n = len(nums)
for i in range(n):
if nums[i] == minK:
m.append(i)
if nums[i] == maxK:
M.append(i)
if nums[i] < minK or maxK < nums[i]:
ob.append(i)
def next(arr, cur):
if len(arr) == 0:
return -1
n = len(arr)
l,r = 0,n-1
if cur < arr[0]:
return arr[0]
if cur >= arr[-1]:
return -1
while l + 1 < r:
m = (l+r) // 2
if arr[m] > cur:
r = m
else:
l = m
return arr[r]

res = 0

if minK == maxK:
for i in range(n):
x = nums[i]
if x == minK:
nextob = next(ob,i)
if nextob == -1:
nextob = n
res += max(0, nextob - i)
return res

for i in range(n):
x = nums[i]
if x == minK:
nextM = next(M,i)
nextob = next(ob,i)
if nextM != -1:
if nextob == -1:
nextob = n
res += max(0, nextob - nextM)
elif x == maxK:
nextm = next(m,i)
nextob = next(ob,i)
if nextm != -1:
if nextob == -1:
nextob = n
res += max(0, nextob - nextm)
elif minK < x < maxK:
nextm = next(m,i)
nextM = next(M,i)
nextob = next(ob,i)
if nextm != -1 and nextM != -1:
if nextob == -1:
nextob = n
res += max(0, nextob - max(nextm, nextM))
return res