मान लीजिए हमें nums नामक संख्याओं की एक सूची दी गई है। हमें मौजूदा चौगुनी (a,b,c,d) की संख्या ज्ञात करनी है जैसे कि anums[a] < nums[b] और nums[c] > nums[d]। सरणी nums पूर्णांकों 1...N का क्रमचय है।
उदाहरण के लिए, nums = [3,4,7,6,5] के लिए आउटपुट 5 होगा।
एल्गोरिदम (बाइनरी सर्च + प्रीफिक्स काउंट)
MOD = 10^9+7- यदि
len(nums) < 4, तो 0 वापस करें ds_smaller_than_c[c]की गणना करें:cके दाएं उन तत्वों की संख्या जोnums[c]as_smaller_than_b_sumको बनाए रखें:bके बाएं उन तत्वों की संख्या जोnums[b]से छोटे हैं- प्रत्येक
bके लिए,quadruplet_count += as_smaller_than_b_sum * ds_smaller_than_c[b+1]quadruplet_count % MODवापस करें
उदाहरण
import bisect
MOD = 10**9+7
class Solution:
def solve(self, nums):
if len(nums) < 4: return 0
n = len(nums)
sorted_ds = [nums[-1]]
sorted_ds.sort()
ds_smaller_than_c = [0]*n
for c in range(n-2, -1, -1):
ds_smaller_than_c[c] = bisect.bisect_right(sorted_ds, nums[c]-1)
sorted_ds.append(nums[c])
sorted_ds.sort()
quadruplet_count = 0
sorted_as = [nums[0]]
sorted_as.sort()
as_smaller_than_b_sum = 0
for b in range(1, n-2):
as_smaller_than_b_sum += bisect.bisect_right(sorted_as, nums[b]-1)
sorted_as.sort()
as_smaller_than_b_sum %= MOD
sorted_as.append(nums[b])
sorted_as.sort()
quadruplet_count += as_smaller_than_b_sum * ds_smaller_than_c[b+1]
quadruplet_count %= MOD
return quadruplet_count
ob = Solution()
print(ob.solve([3,4,7,6,5]))
इनपुट
[3, 4, 7, 6, 5]
आउटपुट
5
