Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int n,st[500500],cnt[500500],last;
long long ans;

int main()
{
    int x;
    cin >> n;
    for (int i=1;i<=n;i++) 
    {
        scanf("%d",&x);
        int j=0,same=0;
        while (last && st[last]<=x) 
        {
            j+=cnt[last]; 
            if (st[last]==x) same=1;
            last--;
        }
        if (st[last]>x) j++;
        if (i>1) ans+=j;
        if (!same) st[++last]=x, cnt[last]=1;
        else cnt[++last]++;
    }
    cout << ans << endl;
}

Code mẫu của happyboy99x

#include<iostream>
#include<stack>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    int n; cin >> n;
    stack<pair<int, int> > st;
    long long res = 0;
    for(int i = 0; i < n; ++i) {
        int a; cin >> a;
        while(!st.empty() && st.top().first < a)
            res += st.top().second, st.pop();
        if(!st.empty()) {
            if(st.top().first == a) {
                res += st.top().second++;
                if(st.size() > 1) ++res;
            } else {
                ++res;
                st.push(make_pair(a, 1));
            }
        } else st.push(make_pair(a, 1));
    }
    cout << res << '\n';
    return 0;
}

Code mẫu của ladpro98

#include <iostream>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
const int N = 500005;
using namespace std;
int a[N], S[N], lazy[N];
int n, top;

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    FOR(i, 0, n) cin >> a[i];
    top = 0; long long ans = 0;
    FOR(i, 0, n) {
        while (top && a[S[top - 1]] < a[i]) ans += lazy[--top];
        if (top && a[S[top - 1]] == a[i]) {
            ans += lazy[top - 1];
            lazy[top - 1]++;
            if (top > 1) ans++;
        }
        else {
            if (top) ans++;
            lazy[top] = 1;
            S[top++] = i;
        }
    }
    cout << ans;
    return 0;
}

Code mẫu của RR

#include <sstream>
#include <iomanip>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++)
#define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--)
#define SET(a,v) memset(a,v,sizeof(a))
#define sqr(x) ((x)*(x))
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair

#define DEBUG(x) cout << #x << " = "; cout << x << endl;
#define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl;
#define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl;
using namespace std;

//Buffer reading
int INP,AM,REACHEOF;
#define BUFSIZE (1<<12)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        if (REACHEOF) return 0;\
        memset(BUF,0,sizeof BUF);\
        int inpzzz = fread(BUF,1,BUFSIZE,stdin);\
        if (inpzzz != BUFSIZE) REACHEOF = true;\
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

const long double PI = acos((long double) -1.0);
const int MN = 500111;

int n, a[MN], st[MN], top;
ll sum[MN], cnt[MN];

void solve() {
    top = 0;
    long long res = 0;
    int u;
    FOR(i,1,n) {
        while (top && a[i] > a[st[top]]) {
            u = st[top];
            res += cnt[top] * ((top > 1) + 1);
            --top;
        }
        if (a[i] == a[st[top]]) {
            res += cnt[top];
            ++cnt[top];
            ++sum[top];
        }
        else {
            ++top;
            st[top] = i;
            cnt[top] = 1;
            sum[top] = sum[top-1] + 1;
        }
    }

    while (top) {
        u = st[top];
        res += cnt[top] * (top > 1);
        --top;
    }
    cout << res << endl;
}

int main() {
    scanf("%d", &n);
    FOR(i,1,n) scanf("%d", &a[i]);

    solve();
    return 0;
}

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAX   500500
#define v   first
#define e   second
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
int a[MAX];
int n;
ll res;
stack<ii> st;
void init(void) {
    scanf("%d",&n);
    int i;
    for (i=1;i<=n;i=i+1) scanf("%d",&a[i]);
}
void process(void) {
    while (!st.empty()) st.pop();
    res=0LL;
    int i;
    for (i=1;i<=n;i=i+1) {
        if (st.empty()) st.push(ii(a[i],1));
        else {
            if (st.top().v>a[i]) {
                res++;
                st.push(ii(a[i],1));
            }
            else if (st.top().v==a[i]) {
                res+=st.top().e+(st.size()>1);
                st.top().e++;
            }
            else {
                while (!st.empty() && st.top().v<a[i]) {
                    res+=st.top().e;
                    st.pop();
                }
                if (st.empty()) st.push(ii(a[i],1));
                else {
                    if (st.top().v==a[i]) {
                        res+=st.top().e+(st.size()>1);
                        st.top().e++;
                    }
                    else {
                        res++;
                        st.push(ii(a[i],1));
                    }
                }
            }
        }
    }
    printf("%lld",res);
}
int main(void) {
    init();
    process();
    return 0;
}