Second Order Difference Array (ABC407F)

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

const int nax = 2e5 + 4;
int n, a[nax];
int L[nax], R[nax];
long long ans[nax];
void PlayGround() {
    cin>>n;
    for(int i=1; i<=n; ++i) {
        cin>>a[i];
    }

    int stk[n + 10] = {0}, top = 0;
    for(int i=1; i<=n; ++i) {
        while(top && a[stk[top]] <= a[i]) R[stk[top--]] = i;
        stk[++top] = i;
    }
    while(top) R[stk[top--]] = n+1;
    for(int i=n; i>0; --i) {
        while(top && a[stk[top]] < a[i]) L[stk[top--]] = i;
        stk[++top] = i;
    }


    //second order difference array works because the number of times a[i]
    //gets added to each subarray length has the following pattern:
    //1 2 3 4 5 6 ... x x x x x x x-1 x-2 x-3 x-4 ... 3 2 1 0
    // in the first order difference array :
    //1 1 1 1 1 1 ... 0 0 0 0 0 0 -1 -1 -1 -1 -1 ... -1 -1 -1 0 0 0 ...
    //in the second order difference array :
    //1 0 0 0 0 0 ... -1 0 0 0 0 0 -1 0 0 0 0 0 0 ... 0 0 0 0 1 0 0 0 ...

    for(int i=1; i<=n; ++i) {
        ans[1] += a[i];
        ans[i - L[i] + 1] -= a[i];
        ans[R[i] - i + 1] -= a[i];
        ans[R[i] - L[i] + 1] += a[i];
    } // now ans is the second order difference array of actual answer
    for(int i=1; i<=n; ++i) {
        ans[i] += ans[i-1];
    } // first order difference array
    for(int i=1; i<=n; ++i) {
        ans[i] += ans[i-1];
    } // actual ans

    for(int i=1; i<=n; ++i) {
        cout<<ans[i]<<'\n';
    }

}
int main() {
    int t = 1;
    while(t--)
        PlayGround();
}