Невозможно решить сумму минимума диапазона с помощью обычной концепции. ⇐ C++

[Anonymous]

Я пытался решить задачу о сумме минимального диапазона лит-кода. Я делал довольно обычные вещи, например, получал индекс предыдущего наименьшего числа и индекс следующего наименьшего числа для каждого номера. хранится так, что я могу найти длину диапазона как i - pse и nse - i, но... это не работает для [71,55,82,55]

Код: Выделить всё

class Solution {
public:
int mod = 1e9 + 7;
int sumSubarrayMins(vector& arr) {
int n = arr.size();
vector nse(n, 0), pse(n,0);
fill(nse, pse, arr, n);
int sum = 0;
for(int i = 0; i st,st2;
pse[0] = -1;
st.push({arr[0],0});
for(int i = 1; i=arr[i]) st.pop();
if(!st.empty()) pse[i] = st.top().second;
else pse[i] = -1;
st.push({arr[i],i});
}
nse[n-1] = n;
st2.push({arr[n-1],n-1});
for(int i = n-2; i>=0;i--){
while(!st2.empty() && st2.top().first>=arr[i]) st2.pop();
if(!st2.empty()) nse[i] = st2.top().second;
else nse[i] = n;
st2.push({arr[i],i});
}
}
};

`


Подробнее здесь: https://stackoverflow.com/questions/788 ... al-concept