Skip to content

1D Prefix Sum

Table of Contents

1310. XOR Queries of a Subarray

2438. Range Product Queries of Powers

1895. Largest Magic Square

1878. Get Biggest Three Rhombus Sums in a Grid

1031. Maximum Sum of Two Non-Overlapping Subarrays

2245. Maximum Trailing Zeros in a Cornered Path

1712. Ways to Split Array Into Three Subarrays

1862. Sum of Floored Pairs

363. Max Sum of Rectangle No Larger Than K

2281. Sum of Total Strength of Wizards

from itertools import accumulate
from typing import List


# Monotonic Stack
def totalStrength(strength: List[int]) -> int:
    n = len(strength)
    left = [-1 for _ in range(n)]
    right = [n for _ in range(n)]
    stack = []

    for i, v in enumerate(strength):
        while stack and strength[stack[-1]] >= v:
            right[stack.pop()] = i
        if stack:
            left[i] = stack[-1]
        stack.append(i)

    prefix_sum = list(accumulate(accumulate(strength, initial=0), initial=0))

    ans = 0
    for i, v in enumerate(strength):
        l, r = left[i] + 1, right[i] - 1
        tot = (i - l + 1) * (prefix_sum[r + 2] - prefix_sum[i + 1]) - (
            r - i + 1
        ) * (prefix_sum[i + 1] - prefix_sum[l])
        ans += v * tot

    return ans % (10**9 + 7)


strength = [1, 3, 1, 2]
print(totalStrength(strength))  # 44

3445. Maximum Difference Between Even and Odd Frequency II

2983. Palindrome Rearrangement Queries

2955. Number of Same-End Substrings

1788. Maximize the Beauty of the Garden

2819. Minimum Relative Loss After Buying Chocolates

Comments