Entering edit mode

**Overview**

- Bob has N chocolates in his refrigerator to which he gives special value.
- He performs some operations on the chocolates.
- In each operation, he takes one or more chocolates that are lying in a continuous manner.
- He then finds and notes down the minimum special value of chocolate in that group of chocolates.
- He performs this operation for all groups of chocolates he could find.
- The task is to find the sum of all the numbers he had written.

**Solution**

- If we try to simplify the problem statement we would find that given an array of n integers,
**we have to find the sum of minimums over all the subarray of this array.** - This can be done in O(n) using the famous stack trick.
- For any index i we can find the
**left_bound**and**right_bound**for it. **left_bound**: Let**l_index**represent the left_bound for an index**i**.**l_index**for an index**i**can be defined as the**index of the rightmost element+1**whose value is**less than or equal to arr[i]**having index less than**i**. If there is no such element, then**left_bound**for an index i will be equal to 0(0-based indexing).To achieve this, we will insert

**only the index of the elements from left to right into the stack**. Let us suppose, we are inserting an index i in the stack and j be the index of the topmost element currently present in the stack.**While the value arr[i] is less than the value at the topmost index in the stack and the stack is not empty, keep popping the elements in the stack**. After the condition is dissatisfied, the**left_bound**for the current index is updated as**the top index in the stack +1 or 0**if the stack is empty.Similarly we can calculate the

**right_bounds**for each index.Now after we have left and right bounds for each index add the following to answer for each index:

```
`ans+= a[i]*((i-left_bound+1)*(right_bound-i+1));`
```

- Now print the final answer.

**Code**

```
ll n;
cin >> n;
vector<ll> a(n);
for (ll i = 0; i < n; i++)
{
cin >> a[i];
}
vector<ll> vminr(n, n - 1), vminl(n, 0);
stack<ll> st;
for (ll i = 0; i < n; i++)
{
while (st.size() && a[st.top()] > a[i]) // while the topmost element is greater than current element keep popping it
{
st.pop();
}
if (st.size())
{
vminl[i] = st.top() + 1; // update the left_bound for the current index
}
st.push(i);
}
while (st.size())
{
st.pop();
}
for (ll i = n - 1; i >= 0; i--)
{
while (st.size() && a[st.top()] >= a[i]) // while the topmost element is greater than or equal to current element keep popping it
{
st.pop();
}
if (st.size())
{
vminr[i] = st.top() - 1; // update the right bound for the current index
}
st.push(i);
}
while (st.size())
{
st.pop();
}
ll ans = 0;
for (ll i = 0; i < n; i++)
{
ll lboundary = vminl[i];
ll rboundary = vminr[i];
ll tot = ((i - lboundary + 1) * (rboundary - i + 1));
ans += (a[i] * tot); // Add element*total_subaarays_it_includes to the final answer
}
cout << ans << endl;
return;
```

Loading Similar Posts

You can validate your code by submitting here: https://www.thejoboverflow.com/problem/243/