Code mẫu

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=1e5+1;
int n;
ll a[N];
ll Mx[100001][20];
ll Mn[100001][20];
map<ll,int> trc;
ll res;
void init()
{
    for (int i=1;i<=n;i++)
        Mx[i][0]=Mn[i][0]=a[i];
    for (int k=1; (1<<k)<=n; k++)
        for (int i=1; i+(1<<k)-1<=n; i++)
        {
            Mx[i][k] = max(Mx[i][k-1],Mx[i+(1<<(k-1))][k-1]);
            Mn[i][k] = min(Mn[i][k-1],Mn[i+(1<<(k-1))][k-1]);
        }
}
ll getmx(int u,int v)
{
    int k=log2(v-u+1);
    return max(Mx[u][k],Mx[v-(1<<k)+1][k]);
}
ll getmn(int u,int v)
{
    int k=log2(v-u+1);
    return min(Mn[u][k],Mn[v-(1<<k)+1][k]);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    freopen("SUDI.inp","r",stdin);
    freopen("SUDI.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];

    }
    init();
    for(int i=1;i<=n;i++)
    {
        int dau=trc[a[i]]+1,cuoi=i,giua;
        int posl=i;
        while(dau<=cuoi)
        {
            giua=(dau+cuoi)/2;
            if(getmx(giua,i)==a[i])
            {
                posl=giua;
                cuoi=giua-1;
            }
            else dau=giua+1;
        }
        dau=i,cuoi=n;
        int posr=i;
        while(dau<=cuoi)
        {
            giua=(dau+cuoi)/2;
            if(getmx(i,giua)==a[i])
            {
                posr=giua;
                dau=giua+1;
            }
            else cuoi=giua-1;
        }
        res+=1LL*(posr-i+1)*(i-posl+1)*a[i];

        dau=trc[a[i]]+1,cuoi=i,giua;
        posl=i;
        while(dau<=cuoi)
        {
            giua=(dau+cuoi)/2;
            if(getmn(giua,i)==a[i])
            {
                posl=giua;
                cuoi=giua-1;
            }
            else dau=giua+1;
        }
        dau=i,cuoi=n;
        posr=i;
        while(dau<=cuoi)
        {
            giua=(dau+cuoi)/2;
            if(getmn(i,giua)==a[i])
            {
                posr=giua;
                dau=giua+1;
            }
            else cuoi=giua-1;
        }
        res-=1LL*(posr-i+1)*(i-posl+1)*a[i];
        trc[a[i]]=i;
    }
    cout<<res;
    return 0;
}