Interesting Problem on Application of Stack

Awesome problem and even an incredible solution.

I was thinking of another approach using Binary Search.

Approach:-

1. Let say at a particular stage we are calculating the subarray A[L..R].
2. Find the index K which is the max of the current subarray in between L and R. (Can be done in O(1) using Sparse Table). In the case of multiple maxima inside the subarray, any maxima index will work.
3. For the current maximum, calculate the answer. For this, count the number of sub-subarrays in the current range L to R. There will be R — K subarray in the right, K — L subarray in the left, and its individual position. We have to find lengths for them and that could be done using AP formula as described above. All will be multiplied with MAXM of that range subarray. So this could be achieved in O(1).
4. After this, call recursively func(L , K — 1) and func(K + 1, R) to calculate its left sub part and right sub part for those subarrays.

In total there will be Log N binary division, and each stage it will be O(1) if used Sparse Table for fetching the maximum inside the range.

Building up Sparse Table would take NlogN time and space.

Total T.C :- NlogN

I believe there is a very similar COCI problem, but I can't find it right now. I will update this post once I find it.

i also thought same like u , but i splitted the above equation into 3 parts like r,-l,+1 and applying summations, also u explained really well

#include<bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define ALL(v) v.begin(), v.end()
#define LSOne(x) (x & (-x))
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long, long> pll;
typedef pair<string, string> pss;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<long> vl;
typedef vector<vl> vvl;

double EPS = 1e-9;
int INF = 1000000005;
long long INFF = 1000000000000000005LL;
double PI = acos(-1);
int dirx[8] = { -1, 0, 0, 1, -1, -1, 1, 1 };
int diry[8] = { 0, 1, -1, 0, -1, 1, -1, 1 };

template<typename T>
void print_vec(vector<T>& A){
    for(T& a : A){
        cout << a << " ";
    }
    cout << "\n";
}

//Suppose the largest element x is at position k
/*
x will occurr in k * (n-k) subarrays 

*/

void fen_update(vector<int>& A, int idx, int k){
    while(idx < A.size()){
        A[idx] += k;
        idx += LSOne(idx);
    }
}

int fen_query(vector<int>& A, int idx){
    int ans = 0;
    while(idx > 0){
        ans += A[idx];
        idx -= LSOne(idx);
    }
    return ans;
}

int range_query(vector<int>& A, int i, int j){
    return fen_query(A, j) - fen_query(A, i-1);
} 

vector<int> calculate(const vector<int>& A, bool reversed = false){
    int n = A.size();
    vector<int> B(n); copy(A.begin(), A.end(),B.begin());
    sort(ALL(B));
    B.resize(unique(B.begin(), B.end()) - B.begin());
    print_vec(B);
    vector<int> Q;
    vector<int> to_left(n, -1);
    vector<int> fenw(n+1, 0);

    Q.push_back(A[0]);
    for(int i = 1; i < n; i++){
        auto it = lower_bound(Q.begin(), Q.end(), A[i], greater<int>());
        if(it == Q.begin()){
            to_left[i] = -1;
        }else{
            it --;
            print_vec(Q);
            cout << (*it) << " " << A[i] << "\n";
            int p = lower_bound(B.begin(), B.end(), *it) - B.begin() + 1;
            int idx = upper_bound(Q.begin(), Q.end(), *it, greater<int>()) - Q.begin() - 1;
            cout << idx << " " << p << "\n";
            cout << "--------" << "\n";
            to_left[i] = idx + fen_query(fenw, p);
            if(reversed){
                to_left[i] = n-1 - to_left[i];
            }
        }
        //cout << it - Q.begin() << "\n";
        //print_vec(Q);

        while(Q.size() > 0 && A[i] >= Q[Q.size()-1]){
            int idx = lower_bound(B.begin(), B.end(), Q[Q.size()-1]) - B.begin() + 1;
            Q.pop_back();
            fen_update(fenw, idx, 1);
        }
        Q.push_back(A[i]);
        //print_vec(Q);
    }
    return to_left;
}

void solve(){
    int n; cin >> n;
    vector<int> A(n);
    for(int i = 0; i < n; i++) cin >> A[i];

    /*
    For each element x at index i, we want to find the
    closes position j < i such that A[j] > x and the closest position
    k > i such that A[k] > x.

    6
    1 3 2 3 5 4

    */

    vector<int> to_left = calculate(A);
    reverse(A.begin(), A.end());
    vector<int> to_right = calculate(A, true);
    reverse(to_right.begin(), to_right.end());
    reverse(A.begin(), A.end());

    vector<ll> C(n+1, 0);
    for(int i = 1; i <= n; i++){
        C[i] = C[i-1] + i*i;
    }

    map<int,int> G;
    ll total = 0;
    for(int i = 0; i < n; i++){
        int l = to_left[i] + 1;
        int r = to_right[i] == -1 ? n-1 : to_right[i] - 1;
        l = max(l, G[A[i]]);

        int cnt = 0;
        cnt += (i-l+1) * (i+r) * (r-i+1)/2;
        cnt -= (r-i+1)*(i-l+1)*(i+l)/2;
        cnt += (i-l+1)*(r-i+1);
        total += A[i] * cnt;
        G[A[i]] = i + 1;
    }

    print_vec(to_left);
    print_vec(to_right);
    cout << total << "\n";
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    while(T--){
        solve();
    }
}

I tried the problem myself without the use of stacks, here is my overcomplicated approach. (coordinate compression + standard fenwick tree) (I'm not 100% about the correctness)

This is actually an aplication of the solution to the maximum rectangle in a histogram problem. I really like it and its cool that you were able to reach this without seeing anything about it before.

I got stuck on the overlap part If find (by stack) left[i] --> <=A[i] and Right[i] --> <=A[i] But there we have many overlap I dont figure out how to handle By seeing your soln i got idea that we have to limit R[i] --> <A[i] so that other is calculated by next similar Thanks for that idea