Editorial for Ripple Effect

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Parsa

Let $S$ ~S~ be the answer to this problem. We know:

$S = \sum_{1 \le i \le j \le n} \big( \max(A[i..j]) - \min(A[i..j]) \big)$ .

We can rewrite $S$ ~S~ as:

$S = \big( \sum_{1 \le i \le j \le n} \max(A[i..j]) \big) - \big( \sum_{1 \le i \le j \le n} \min(A[i..j]) \big)$ .

This means we can calculate the total contribution of each element of $A$ ~A~ separately—once for when it acts as the maximum in a subarray, and once for when it acts as the minimum.

Step 1 — Contribution as Minimum

For each $A_i$ ~A_i~, find:

$L_{\min}$ ~L_{\min}~ = index of the closest element to the left of $i$ ~i~ that is strictly smaller than $A_i$ ~A_i~ (or 0 if none exists),
$R_{\min}$ ~R_{\min}~ = index of the closest element to the right of $i$ ~i~ that is smaller or equal to $A_i$ ~A_i~ (or n+1 if none exists).

In all subarrays of the form $A[L_{\min}+1 .. k]$ ~A[L_{\min}+1 .. k]~ with $k \le R_{\min}-1$ ~k \le R_{\min}-1~ that include $A_i$ ~A_i~, $A_i$ ~A_i~ is the minimum element.
The number of such subarrays is:

$(i - L_{\min}) \times (R_{\min} - i)$ ~(i - L_{\min}) \times (R_{\min} - i)~.

Thus, $A_i$ ~A_i~ contributes:

$-1 \times (i - L_{\min}) \times (R_{\min} - i) \times A_i$ to $S$ ~S~.

Step 2 — Contribution as Maximum

Similarly, find:

$L_{\max}$ ~L_{\max}~ = index of the closest element to the left of $i$ ~i~ that is strictly greater than $A_i$ ~A_i~ (or 0 if none exists),
$R_{\max}$ ~R_{\max}~ = index of the closest element to the right of $i$ ~i~ that is greater or equal to $A_i$ ~A_i~ (or n+1 if none exists).

The number of subarrays where $A_i$ ~A_i~ is the maximum is:

$(i - L_{\max}) \times (R_{\max} - i)$ ~(i - L_{\max}) \times (R_{\max} - i)~.

Thus, $A_i$ ~A_i~ contributes:

$+1 \times (i - L_{\max}) \times (R_{\max} - i) \times A_i$ to $S$ ~S~.

We compute $S$ ~S~ by summing the contributions of all elements for both their maximum and minimum roles:

$S = \sum_{i=1}^n \Big[ (i - L_{\max}) \times (R_{\max} - i) \times A_i - (i - L_{\min}) \times (R_{\min} - i) \times A_i \Big]$ .

Both $L_{\min}, R_{\min}$ ~L_{\min}, R_{\min}~ and $L_{\max}, R_{\max}$ ~L_{\max}, R_{\max}~ can be found in $O(n)$ ~O(n)~ using monotonic stacks.

C++ Solution:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> arr(n);
    for (auto& x: arr) cin >> x;

    vector<long long> lMin(n), rMin(n);
    vector<long long> lMax(n), rMax(n);

    stack<int> s;

    for (int i = 0; i < n; i++) {
        while (!s.empty() && arr[s.top()] >= arr[i])
            s.pop();
        lMin[i] = s.empty() ? -1 : s.top();
        s.push(i);
    }

    while (!s.empty()) s.pop();

    for (int i = n - 1; i >= 0; i--) {
        while (!s.empty() && arr[s.top()] > arr[i])
            s.pop();
        rMin[i] = s.empty() ? n : s.top();
        s.push(i);
    }

    while (!s.empty()) s.pop();

    for (int i = 0; i < n; i++) {
        while (!s.empty() && arr[s.top()] <= arr[i])
            s.pop();
        lMax[i] = s.empty() ? -1 : s.top();
        s.push(i);
    }

    while (!s.empty()) s.pop();

    for (int i = n - 1; i >= 0; i--) {
        while (!s.empty() && arr[s.top()] < arr[i])
            s.pop();
        rMax[i] = s.empty() ? n : s.top();
        s.push(i);
    }

    long long result = 0;
    for (int i = 0; i < n; i++) {
        // Count subarrays where arr[i] is maximum
        long long maxCount = (long long)(i - lMax[i]) * (rMax[i] - i);

        // Count subarrays where arr[i] is minimum  
        long long minCount = (long long)(i - lMin[i]) * (rMin[i] - i);

        result += (long long)arr[i] * (maxCount - minCount);
    }
    cout << result << endl;
}

Python Solution:

n = int(input())
A = list(map(int, input().split()))

lMin, lMax, rMin, rMax = [[0 for _ in range(n)] for _ in range(4)]

maxS, minS = [], []
for i in range(n):
    while maxS and A[maxS[-1]] <= A[i]:
        maxS.pop()
    while minS and A[minS[-1]] >= A[i]:
        minS.pop()

    lMin[i] = minS[-1] if minS else -1
    lMax[i] = maxS[-1] if maxS else -1
    maxS.append(i)
    minS.append(i)

maxS.clear()
minS.clear()

for i in range(n)[::-1]:
    while maxS and A[maxS[-1]] < A[i]:
        maxS.pop()
    while minS and A[minS[-1]] > A[i]:
        minS.pop()

    rMin[i] = minS[-1] if minS else n
    rMax[i] = maxS[-1] if maxS else n
    maxS.append(i)
    minS.append(i)

res = 0
# Add the maxsum and subtract the minsum
for i, (l, r) in enumerate(zip(lMax, rMax)):
    res += A[i]*(i-l)*(r-i)
for i, (l,r) in enumerate(zip(lMin, rMin)):
    res -= A[i]*(i-l)*(r-i)

print(res)

Comments

There are no comments at the moment.