# Gojo - Editorial

# MiniMaxi - Editorial

Đầu tiên, ta có thể nhìn bài toán theo hướng khác, thay vì tính tất cả $f(l,r)$ theo $max(a_i) - min(a_i) \forall (l \le i \le r)$, ta sẽ tính tổng các $max(a_i) \forall (l \le i \le r)$ trước, rồi trừ đi các $min(a_i) \forall (l \le i \le r)$.

Tính $max$:

- Gọi $L_i$ là vị trí nhỏ nhất mà $a_i > a_j \forall (L_i \le j \le i-1)$. Gọi $R_i$ là vị trí lớn nhất mà $a_i \ge a_j \forall (i+1 \le j \le R_i)$. Dãy $L_i$ và $R_i$ có thể dùng $stack$ để tính trong $O(N)$, nếu chưa biết bạn có thể tham khảo tại [đây](https://vnoi.info/wiki/algo/data-structures/Stack.md).

- Như vậy với mỗi vị trí $i$, giá trị $a_i$ sẽ được cộng vào kết quả $(i-L_i+1)*(R_i-i+1)$ lần. Cứ làm như vậy với mọi i, ta sẽ tính được tổng của các $max$.
- Để hiểu tại sao ở đoạn $L_i$ ta lấy $a_i > a_j$ mà không lấy $a_i \ge a_j$ như ở đoạn tính $R_i$, bạn có thể tham khảo test sau:
+ 3

3 1 3

Làm tương tự khi tính $min$, nhưng lần này, thay vì cộng vào kết quả, ta trừ nó vào kết quả.

Độ phức tạp: $O(N)$

Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5;
int n,m;
int a[N],b[N];
int res=0;
int l[N], r[N];
void minn(int c[]){
	stack<int> st;
	for (int i=1; i<=m; i++) {
		while (!st.empty()&&c[i]<c[st.top()]) st.pop();
		l[i] = st.empty() ? 1 : st.top()+1;
		st.push(i);	
	}
	stack<int> s;
	for (int i=m; i>=1; i--){
		while (!s.empty()&&c[i]<=c[s.top()]) s.pop();
		r[i] = s.empty() ? m : s.top()-1;
		s.push(i);	
	}
	for (int i=1; i<=m; i++) {
	//	cout << l[i] << ' ' << r[i] << '\n';
		res-=a[i]*(i-l[i]+1)*(r[i]-i+1);
	}	
}
void maxx(int c[]){
	stack<int> st;
	for (int i=1; i<=m; i++) {
		while (!st.empty()&&c[i]>c[st.top()]) st.pop();
		l[i] = st.empty() ? 1 : st.top()+1;
		st.push(i);	
	}
	stack<int> s;
	for (int i=m; i>=1; i--){
		while (!s.empty()&&c[i]>=c[s.top()]) s.pop();
		r[i] = s.empty() ? m : s.top()-1;
		s.push(i);	
	}
	for (int i=1; i<=m; i++) {
	//	cout << l[i] << ' ' << r[i]<< '\n';
		res+=a[i]*(i-l[i]+1)*(r[i]-i+1);
	}	
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>m;
	for (int i=1; i<=m; i++) cin>>a[i];
	minn(a);
	for (int i=1; i<=m; i++) l[i]=r[i]=0;
	maxx(a); 
	cout << res;
}

# NRect - Editorial

Nếu ta có thể tính được hàm $cal(x)$ là số hình chữ nhật có $min \ge x$, thì kết quả của bài toán sẽ là $cal(100) - cal(101)$.

Để tính hàm $cal(x)$, ta có thể quy về một bài toán mới, gọi ma trận $b$ gồm $n$ hàng và $n$ cột, $b_{ij} = 0$ nếu $a_{ij} < x$, ngược lại $b_{ij} = 1$.

Bài toán lúc này chuyển thành đếm số hình chữ nhật trong ma trận $b$ gồm toàn số $1$. Để làm được điều này, ta làm như sau:
- Cố định từng hàng, có thể coi đây là *đáy* của hình chữ nhật ta đang xét.
- Sau đó, giả sử ta đang cố định hàng $i$, gọi $h_j$ là số số $1$ liên tiếp trên cột $j$ bắt đầu từ đáy là hàng $i$:
- Gọi $l_j$ là vị trí xa nhất về bên trái mà $h_j$ là $min$ trên đoạn $[l_j,j]$, $r_j$ là vị trí xa nhất về bên phải mà $h_j$ là $min$ **và không có số nào bằng với h_j** trên đoạn $[j,r_j]$.
- Dễ thấy, kết quả lúc này sẽ cộng thêm $(r[j] - j + 1) * (j - l[j] + 1)*h[i][j]$.
- Việc $r_j$ thêm điều kiện **không có số nào bằng với h_j** sẽ đảm bảo ta không tính trùng hình chữ nhật.
- Hai mảng $l$, $r$ có thể dễ dàng tính bằng $stack$.

Độ phức tạp: $O(n^2)$.

Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
const int N = 1005;
int a[N][N];
int c[N][N];
int h[N][N];
int l[N],r[N];
int solve (int val) {
	int res = 0;
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=n; j++) {
			c[i][j] = a[i][j] >= val;
		//	cout << c[i][j] << ' ';
		} 
	//	cout << '\n';
	}
//	cout << "??\n";
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=n; j++) {
			if (c[i][j]) {
				h[i][j] = h[i-1][j] + 1;
			}
			else h[i][j] = 0;
		}
	}
	
	for (int i=1; i<=n; i++) {
		stack<int> st;
		st.push(0);
		for (int j=1; j<=n; j++) {
			while (st.size() >= 2 && h[i][st.top()] >= h[i][j]) st.pop();
			l[j] = st.top() + 1;
			st.push(j);
		}
		while (st.size()) st.pop();
		st.push(n+1);
		for (int j=n; j>=1; j--) {
			while (st.size() >= 2 && h[i][st.top()] > h[i][j]) st.pop();
			r[j] = st.top() - 1;
			st.push(j);
			res += (r[j] - j + 1) * (j - l[j] + 1)*h[i][j];
	//		cout << i << ' ' << j << ' ' << l[j] << ' ' << r[j] << '\n';
		}
	}
//	cout << res << "?\n";
	return res;
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=n; j++) cin >> a[i][j];
	}
	cout << solve (100) - solve(101);
}