Editorial for Bob xây nhà

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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];
}

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;
}
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;
}
}
return 0;
}


#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;
}