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>
using namespace std;

int n, a[10100], cnt[10100][10100];

int countInterval(int l, int r, int minVal, int maxVal)
{
    if (l > r || maxVal < minVal) return 0;
    return cnt[r][maxVal] - cnt[l - 1][maxVal] - cnt[r][minVal - 1] + cnt[l - 1][minVal - 1];
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        for (int j = 1; j < a[i]; j++) cnt[i][j] = cnt[i - 1][j];
        for (int j = a[i]; j <= n; j++) cnt[i][j] = cnt[i - 1][j] + 1;
    }

    // count (3, 1/4, 2}
    long long ans = 0;
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++)
            if (a[i] > a[j])
                ans += 1LL * countInterval(i + 1, j - 1, a[i] + 1, n) * countInterval(i + 1, j - 1, 1, a[j] - 1);

    // count (3, 4, 1, 2)
    for (int i = 1; i < n; i++)
        for (int j = i + 2; j < n; j++)
            ans -= 1LL * countInterval(i + 1, j - 1, a[i] + 1, n) * countInterval(j + 1, n, a[j] + 1, a[i] - 1);

    cout << ans << endl;
}

Code mẫu của ladpro98

#include <cstdio>
#define N 10000
int a[N], L[N], R[N];

main() {
    int n; scanf("%d", &n);
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%d", a + i);
        int c = 0;
        for (int j = 0; j < i; ++j)
            if (a[j] < a[i])
                ans += c, ++R[j], ++L[i];
            else
                c += R[j] - L[j] + L[i];
    }
    printf("%lld", ans);
}

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;
const int BUFSIZE = (1<<12) + 17;
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp && !REACHEOF) { \
        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 = 10111;

int n, a[MN];
int f[MN][MN], g[MN][MN];

int main() {
    scanf("%d", &n); FOR(i,1,n) scanf("%d", &a[i]);
    FOR(i,1,n) {
        FOR(x,1,n) f[i][x] = f[i-1][x] + (a[i] < x);
        FOR(x,1,n) g[i][x] = g[i-1][x] + (a[i] > x);
    }

    long long res1 = 0, res2 = 0;
    FOR(i3,1,n) FOR(i2,i3+3,n) if (a[i3] > a[i2]) {
        res1 += (g[i2-1][a[i3]] - g[i3][a[i3]]) * (long long) (f[i2-1][a[i2]] - f[i3][a[i2]]);
    }
    FOR(i3,1,n) FOR(i1,i3+2,n) if (a[i3] > a[i1]) {
        res2 += (g[i1-1][a[i3]] - g[i3][a[i3]])
                * (long long) (f[n][a[i3]] - f[i1][a[i3]] - f[n][a[i1]] + f[i1][a[i1]]);
    }
    cout << res1 - res2 << endl;
    return 0;

    long long res = 0;
    FOR(i3,1,n) FOR(i1,i3+1,n) FOR(i4,i1+1,n) FOR(i2,i4+1,n)
        if (a[i1] < a[i2] && a[i2] < a[i3] && a[i3] < a[i4])
            ++res;
    FOR(i3,1,n) FOR(i4,i3+1,n) FOR(i1,i4+1,n) FOR(i2,i1+1,n)
        if (a[i1] < a[i2] && a[i2] < a[i3] && a[i3] < a[i4])
            ++res;
    cout << res << endl;
    return 0;
}