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 happyboy99x

#include <iostream>
using namespace std;

const int LOG_N = 9;
const int N = 1000;
int minPosition[N][LOG_N + 1];
int lg2[N + 1];
int height[N];
int a[N][N];
int leftBound[N];
int rightBound[N];
int m;
int n;

int getMinPosition(int left, int right) {
    int k = lg2[right - left];
    int x = minPosition[left][k];
    int y = minPosition[right - (1 << k)][k];
    return height[x] < height[y] ? x : y;
}

long long calc(int left, int right) {
    if (left >= right) return 0;
    if (left + 1 == right) return height[left];
    int middle = getMinPosition(left, right);
    long long answer = calc(left, middle) + calc(middle + 1, right);
    int le = max(leftBound[middle], left);
    int ri = min(rightBound[middle], right);
    answer += 1LL * (middle - le + 1) * (ri - middle) * height[middle];
    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> m >> n;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            cin >> a[i][j];
    for (int i = 1, j = 0; i <= n; ++i) {
        while (1 << (j + 1) <= i) ++j;
        lg2[i] = j;
    }
    long long answer = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j)
            height[j] = i == 0 || a[i][j] != a[i - 1][j] ? 1 : height[j] + 1;
        for (int j = 0; j < n; ++j)
            minPosition[j][0] = j;
        for (int k = 1; 1 << k <= n; ++k)
            for (int j = 0; j + (1 << k) <= n; ++j) {
                int x = minPosition[j][k - 1];
                int y = minPosition[j + (1 << (k - 1))][k - 1];
                minPosition[j][k] = height[x] < height[y] ? x : y;
            }
        for (int j = 0; j < n; ) {
            int k = j;
            while (k < n && a[i][j] == a[i][k]) ++k;
            for (int z = j; z < k; ++z) {
                leftBound[z] = j;
                rightBound[z] = k;
            }
            j = k;
        }
        answer += calc(0, n);
    }
    cout << answer << '\n';
    return 0;
}

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 1010;
using namespace std;
int m, n;
int a[N][N], H[N], L[N], R[N];

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> m >> n;
    REP(i, 1, m) REP(j, 1, n) cin >> a[i][j];
    LL ans = 0;
    REP(i, 1, m) {
        REP(j, 1, n) if (a[i][j] == a[i - 1][j]) H[j]++; else H[j] = 1;
        L[1] = 0;
        REP(j, 2, n) {
            int k = j - 1;
            while (k && a[i][k] == a[i][j] && H[k] > H[j]) k = L[k];
            L[j] = k;
        }
        R[n] = n + 1;
        REPD(j, n - 1, 1) {
            int k = j + 1;
            while (k <= n && a[i][k] == a[i][j] && H[k] >= H[j]) k = R[k];
            R[j] = k;
        }
        REP(j, 1, n)
        ans += (j - L[j]) * (R[j] - j) * H[j];
    }
    cout << ans;
    return 0;
}

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAX   1111
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
using namespace std;
typedef long long ll;
int a[MAX][MAX],toRight[MAX][MAX];
int tmp[MAX],rangeLeft[MAX],rangeRight[MAX];
int m,n;
void init(void) {
    scanf("%d%d",&m,&n);
    FOR(i,1,m) FOR(j,1,n) scanf("%d",&a[i][j]);
    FOR(i,1,m) FORD(j,n,1) {
        if (j==n) toRight[i][j]=1;
        else toRight[i][j]=a[i][j]==a[i][j+1]?toRight[i][j+1]+1:1;
    }
}
ll countWay(const vector<int> &v) {
    if (v.empty()) return (0);
    int n=v.size();
    FOR(i,1,n) tmp[i]=v[i-1];
    stack<int> st;
    FOR(i,1,n) {
        while (!st.empty() && tmp[st.top()]>tmp[i]) st.pop();
        rangeLeft[i]=st.empty()?1:st.top()+1;
        while (!st.empty() && tmp[st.top()]>=tmp[i]) st.pop();
        st.push(i);
    }
    while (!st.empty()) st.pop();
    FORD(i,n,1) {
        while (!st.empty() && tmp[st.top()]>=tmp[i]) st.pop();
        rangeRight[i]=st.empty()?n:st.top()-1;
        st.push(i);
    }
    ll res=0;
    FOR(i,1,n) res+=1LL*tmp[i]*(rangeRight[i]-i+1)*(i-rangeLeft[i]+1);
    return (res);
}
void process(void) {
    ll res=0;
    FOR(j,1,n) {
        int i=1;
        while (i<=m) {
            vector<int> v;
            v.push_back(toRight[i][j]);
            while (i<m && a[i][j]==a[i+1][j]) {
                i++;
                v.push_back(toRight[i][j]);
            }
            res+=countWay(v);
            i++;
        }
    }
    cout<<res;
}
int main(void) {
    init();
    process();
    return 0;
}