# THI THỬ HSG TỈNH K10+11 - 2025 - II

>[!Note] Thông tin
>Sau đây là lời giải của đề thi thử Kỳ thi Chọn HSG tỉnh Bà Rịa - Vũng Tàu K10+11 lần II (được chuẩn bị theo **ma trận kiến thức của Sở GD&ĐT tỉnh Bà Rịa - Vũng Tàu**)
>
>**Thời gian:** 20:00 - 23:00 ngày 06/03/2025
>
>**Bạn đọc có thể nộp và chấm bài** [TẠI ĐÂY](https://chuyentinbrvt.online/contest/algi_mockhsg1011lan2_2025)
>
>:::info
>Chuẩn bị bởi ==team Logica==, thuộc khuôn khổ dự án [**The Algitect (ALGI Project)**](https://www.facebook.com/algitect.project)
>:::

[toc]

## Bài 1: Liên lạc (4 điểm)

### Tóm tắt đề bài:

Cho ví trí của $n$ chiến binh trong mặt phẳng tọa độ $Ox$, chiến binh thứ $i$ ở vị trí $p_i$ và có thể liên lạc được với những người trong khoảng cách $\left[p_i-R,p_i+R\right]$.

**Yêu cầu:** Tìm $R$ bé nhất để mỗi chiến binh có thể liên lạc được với ==ít nhất $1$ chiến binh khác==.

**Subtask:**
- $25\%$ số điểm: $n \le 10^3$.
- $25\%$ số diểm: $n \le 10^5$ và $p_1 \le p_2 \le \dots \le p_n$.
- $50\%$ số diểm: $n \le 10^5$.

### Mô hình hóa bài toán:

Cho $n$ số nguyên $p_1, p_2, \dots, p_n$.

**Yêu cầu:** Tìm $R$ nhỏ nhất để với mỗi chỉ số $i$ luôn tìm được chỉ số $j \not = i$ thỏa ==$| p_i - p_j | \le R$==

>[!Tip]
>Gọi $R_i$ là khoảng cách $R$ nhỏ nhất để người lính thứ $i$ liên lạc được với ít nhất $1$ người khác
>
>Đáp án của bài toán khi đó là ==$\max(R_1,R_2,\dots,R_n)$==.
>
>:::success
>Như vậy, trọng tâm của bài là tìm $R_i$ với $i$ từ $1$ đến $n$.
>:::

### Subtask 1

Với mỗi phần tử $p_i$, duyệt qua mọi phần tử $p_j$ mà $j \not = i$, khi đó:
$$
R_i = \min(|p_i - p_j|)
$$

**Độ phức tạp thời gian:** $O \left( n^2 \right)$.

:::success
:::spoiler Code

#include<bits/stdc++.h>
using namespace std;

int n, A[1005], ans;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
    }
    
    for (int i = 1; i <= n; i++) {
        int R = INT_MAX;
        for (int j = 1; j <= n; j++) {
            if (i != j) {
                R = min(R, abs(A[i] - A[j]));
            }
        }
        
        ans = max(ans, R);
    }
    
    cout << ans;
}

:::

### Subtask 2

>[!Tip] Nhận xét
> Với mỗi $p_i$, giá trị $p_j$ để $|p_i - p_j|$ đạt giá trị nhỏ nhất là giá trị ==gần với== $p_i$ nhất.

Vì danh sách đã được sắp xếp, nên với mỗi $p_i$ thì giá trị $p_j$ tối ưu chỉ có thể rơi vào $p_{i+1}$ hoặc $p_{i-1}$ (hai số nằm kề $p_i$).

Như vậy, duyệt qua mọi $p_i$ với $i$ từ $1$ đến $n$, và tính:
$$
R_i = \min \left( p_i-p_{i-1}, p_{i+1}-p_i \right)
$$

**Độ phức tạp thời gian:** $O \left( n \right)$.

:::success
:::spoiler Code

#include<bits/stdc++.h>
using namespace std;

int n, A[100005], ans;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
    }
    
    ans = max(R[2] - R[1], R[n] - R[n-1])
    for (int i = 2; i <= n-1; i++) {
        int R1 = A[i] - A[i-1];
        int R2 = A[i+1] - A[i];
        ans = max(ans, min(R1, R2));
    }
    
    cout << ans;
}

:::

### Subtask 3

Kế thừa tư tưởng của subtask trước. Ta chỉ cần sắp xếp lại danh sách $p$, khi đó có thể áp dụng thuật toán y hệt.

**Độ phức tạp thời gian:** $O \left( n \log n \right)$.

:::success
:::spoiler Code

#include<bits/stdc++.h>
using namespace std;

int n, A[100005], ans;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
    }
    
    sort(A+1, A+1+n);
    ans = max(R[2] - R[1], R[n] - R[n-1])
    for (int i = 2; i <= n-1; i++) {
        int R1 = A[i] - A[i-1];
        int R2 = A[i+1] - A[i];
        ans = max(ans, min(R1, R2));
    }
    
    cout << ans;
}

:::

## Bài 2: Chính phương (5 điểm)

### Tóm tắt đề bài:

Cho $n$ số nguyên dương $A_1, A_2, \dots, A_n$, đếm số cặp $i \lt j$ sao cho $A_i \cdot A_j$ là một ==số chính phương==.

**Subtask:**
- $50\%$ số điểm: $1 \le n \le 10^3$.
- $50\%$ số điểm: $1 \le n \le 3 \cdot 10^5$.

### Subtask 1

Dùng hai vòng lặp để xét mọi cặp $\left(i, j \right)$ và đếm số cặp có tích $A_i \cdot A_j$ là số chính phương.
>[!Tip]**Hướng dẫn kiểm tra số chính phương:**
>Vì ==số chính phương== là bình phương của một số nguyên, nên có thể kiểm tra một số $x$ có phải số chính phương hay không bằng cách kiểm tra $\sqrt{x}$ có nguyên hay không.
>
>:::success
>Tuy nhiên, trong Tin học thường hạn chế sử dụng kiểu số thức. Do đó có một cách kiểm tra nhanh gọn hơn: ==so sánh $\left \lfloor \sqrt{x} \right \rfloor ^ 2$ với $x$==.
>:::
>:::spoiler Hàm kiểm tra số chính phương mẫu
>```cpp=1
>bool Check(int x) {
> int tmp = floor(sqrt(x));
> if (tmp * tmp == x) {
> return true;
> }
> else {
> return false;
> }
>}
>```
>:::

**Độ phức tạp thời gian:** $O \left( n^2 \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1003;
int n, A[N], res = 0;

bool check(int x) {
	int tmp = floor(sqrt(x));
	if (tmp * tmp == x) {
        return true;
    }
	else {
        return false;
    }
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> A[i];
    }

    for (int i = 1; i <= n - 1; i++) {
        for (int j = i+1; j <= n; j++) {
            if (check(A[i] * A[j]) == true) {
                res++;
            }
        }
    }

    cout << res;

    return 0;
}

:::

### Subtask 2

>[!Tip] Nhận xét về số chính phương:
>Khi phân tích thừa số nguyên tố của $x$, ta có:
>$$
>\begin{flalign}
>&x = {p_1}^{a_1} \cdot {p_2}^{a_2} \cdot {p_3}^{a_3} \cdots {p_k}^{a_k} \\
>\Leftrightarrow \; &x^2 = \left({p_1}^{a_1} \cdot {p_2}^{a_2} \cdot {p_3}^{a_3} \cdots {p_k}^{a_k} \right)^2 \\
>\Leftrightarrow \; &x^2 = {p_1}^{2 \cdot a_1} \cdot {p_2}^{2 \cdot a_2} \cdot {p_3}^{2 \cdot a_3} \cdots {p_k}^{2 \cdot a_k}
>\end{flalign}
>$$
> Với $p_i$ là thừa số nguyên tố thứ $i$ và $a_i$ là số mũ của thừa số nguyên tố thứ $i$.
>:::success
>Như vậy, số chính phương có ==số mũ của các thừa số nguyên tố== đều là ==số chẵn==.
>:::

Giả sử khi phân tích thừa số nguyên tố của $A_i$, thu được $b_1, b_2, b_3, \dots, b_m$ là các thừa số có số mũ lẻ. Để tích $A_i \cdot A_j$ là một số chính phương thì $A_j$ cũng phải có cùng các thừa số nguyên tố có số mũ lẻ là $b_1, b_2, b_3, \dots, b_m$.
> Vì khi nhân $A_i$ với $A_j$, số mũ của của các thừa số nguyên tố sẽ được cộng vào:
> $$
> b_i^x \cdot b_i^y = b_i^{x+y}
> $$
> Nếu một trong hai số $x$ và $y$ lẻ, số còn lại cũng phải lẻ để đảm bảo $x + y$ chẵn.

Nói cách khác, $A_i$ và $A_j$ có cùng tích của các thừa số nguyên tố mũ lẻ $\left(b_1 \cdot b_2 \cdot b_3 \cdots b_m \right)$.
> Có thể đơn giản hóa như vậy vì $b_i$ là số nguyên tố, nên mỗi bộ sẽ cho ra tích khác nhau

>[!Important]
>Bài toán bây giờ đã trở thành đếm số cặp $i \lt j$ sao cho $f \left(A_i \right) = f \left(A_j \right)$, với $f\left(x\right)$ là tích các thừa số nguyên tố mũ lẻ của $x$.

Để phân tích thừa số nguyên tố của $n$ số nguyên $A_i$ thành các thừa số nguyên tố, theo cách thông thường sẽ có độ phức tạp là $O\left( \sum_{i=1}^n \sqrt{A_i}\right)$, dẫn đến chạy quá thời gian.

Giả sử ta có $E_i$ là ước nguyên tố nhỏ nhất của $i$. Khi đó, để phân tích thừa số nguyên tố của $A_i$, ta liên tục chia $A_i$ cho $E_{A_i}$ đến khi $A_i = 1$.
>VD: Phân tích thừa số nguyên tố của $n = 40$
> - $E_{40} = 2 \rightarrow n = \frac{40}{2} = 20$
> - $E_{20} = 2 \rightarrow n = \frac{20}{2} = 10$
> - $E_{10} = 2 \rightarrow n = \frac{10}{2} = 5$
> - $E_{5} = 5 \rightarrow n = \frac{5}{5} = 1$
>
> Như vậy, $n = 40 = 2^2 \cdot 5^2$.

Vì trong mỗi thao tác, ta chia $A_i$ cho ít nhất là $2$ nên số thao tác tối đa là $\log_2 A_i$.

>[!Tip] Hướng dẫn
> Việc thực hiện tính trước mảng $E$ thường được gọi là ==sàng ước nguyên tố==. Đúng như tên gọi của nó, phương pháp này áp dụng tư tưởng của thuật toán ==sàng nguyên tố==.
> :::success
> Cụ thể, ta duyệt $i$ từ $2$ đến $n$ (với $n$ là giá trị lớn nhất cần sàng tới), nếu $i$ chưa tìm được ước nguyên tố $(E_i = 0)$, ==$i$ là số nguyên tố==, và ta duyệt qua tất cả các bội của $j$ $\left( i, i \cdot 2, i \cdot 3, \dots \right)$ và đánh dấu $E_j = i$.
> :::
> Vì với mỗi số, ta duyệt qua các bội của nó, do đó thuật toán trên có độ phức tạp:
> $$
> O \left( \frac n1 + \frac n2 + \frac n2 \dots \right) \approx O \left( n \log n \right)
> $$
> :::warning
> Tuy nhiên, trong thực tế, thuật toán trên chạy nhanh hơn rất nhiều vì **ta chỉ duyệt qua bội của những số nguyên tố**.
> :::

Như vậy, ta duyệt qua $A_i$ với $i$ từ $1$ đến $n$, lưu mảng đánh dấu $\operatorname{cnt}$ với $\operatorname{cnt}_x$ là số lượng $f\left(A_j\right) = x$ với $1 \le u \lt i$.
>Với $x = {p_1}^{a_1} \cdot {p_2}^{a_2} \cdot {p_3}^{a_3} \cdots {p_k}^{a_k}$ và $f\left(x\right) = b_1 \cdot b_2 \cdot b_3 \cdots b_m$, ta có:
>$$
>\begin{flalign}
>\{b_1, b_2, b_3, \dots, b_m\} &\subset \{{p_1}, {p_2}, {p_3}, \dots, {p_k} \} \\
>\Rightarrow b_1 \cdot b_2 \cdot b_3 \cdots b_m &\le {p_1} \cdot {p_2} \cdot {p_3} \cdots {p_k}\\
>\Leftrightarrow f\left(x\right) \le &\; x \le 10^6
>\end{flalign}
>$$
>Sử dụng mảng đếm là khả thi, không cần sử dụng **map**.

Đáp án khi đó là tổng $\operatorname{cnt}_{A_i}$ với $i$ từ $1$ đến $n$.

**Độ phức tạp thời gian:** $O\left( \log A_1 + \log A_2 + \dots + \log A_n \right) = O\left( \sum_{i=1}^n \log{A_i}\right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
int n, E[N], A[N], cnt[N], pw[N+1];
long long res;

//Sàng ước nguyên tố
void sieve() {
    E[1] = 1;
    for (int p = 2; p <= 1e6; p++) {
        if (E[p] == 0) {
            for (int j = p; j <= 1e6; j += p) {
                E[j] = p;
            }
        }
    }
}

int main(){
    sieve();

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
        
        vector<int> prime_factors;
        while (A[i] > 1) {
            pw[E[A[i]]]++;
            prime_factors.push_back(E[A[i]]);
            A[i] /= E[A[i]];
        }
        
        sort(prime_factors.begin(), prime_factors.end());
        prime_factors.erase(unique(prime_factors.begin(), prime_factors.end()), prime_factors.end());

        int odd = 1;
        for (auto i : prime_factors) {
            if (pw[i] % 2 == 1) {
                odd *= i;
            }
            
            pw[i] = 0;
        }

        res += cnt[odd];
        cnt[odd]++;
    }

    cout << res;

    return 0;
}

:::

## Bài 3: Giải mã (6 điểm)

### Tóm tắt đề bài:

Cho dãy số nguyên gồm $n$ phần tử $A_1, A_2, \dots, A_n$. Biết rằng **độ lệch** một của đoạn con liên tiếp là hiệu lớn nhất giữa hai phần tử bất kỳ trong đoạn.

**Yêu cầu:** Tính giá trị của mọi đoạn con liên tiếp trong dãy. Đáp án chia dư cho $10^9+7$.

**Subtask:**
- $30\%$ số điểm: $n \le 10^3$.
- $30\%$ số điểm: $n \le 10^5$ và $A_i$ phân biệt.
- $20\%$ số điểm: $A_1 \le p_2 \le \dots \le A_n$.
- $20\%$ số điểm: $n \le 2 \cdot 10^6$.

### Mô hình hóa bài toán

Cho dãy số nguyên gồm $n$ phần tử $A_1, A_2, \dots, A_n$. Tính:
$$
\sum_{i = 1}^n \sum_{j = i}^n \left[ \max \left( A_i, A_{i+1}, \dots, A_j\right) - \min \left( A_i, A_{i+1}, \dots, A_j\right) \right] \bmod \left( 10^9 + 7 \right)
$$

### Subtask 1:

Dùng hai vòng lặp để duyệt qua tất cả các đoạn con liên tiếp $[i, j]$, sau đó cộng độ lệch của tất cả các đoạn con lại để được đáp án.

**Độ phức tạp thời gian:** $O \left( n^2 \right)$.

:::success
:::spoiler Code

#include<bits/stdc++.h>
using namespace std;

const int N = 1e3, MOD = 1e9+7;

int n, A[N+5];
long long ans;

main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
    }
    for (int i = 1; i <= n; i++) {
        int tmin = INT_MAX, tmax = INT_MIN;
        for (int j = i; j >= 1; j--) {
            tmin = min(tmin, A[j]);
            tmax = max(tmax, A[j]);
            
            ans += (tmax - tmin);
            ans %= MOD;
        }
    }
    
    cout << ans;
}

:::

### Subtask 2

>[!Tip] Ý tưởng "chìa khóa"
> Có thể thấy, bài toán đang xoay quanh việc tính cho **tất cả các đoạn con**. Rõ ràng đây là một phạm vi rất lớn.
>
>Thay vào đó, ta hãy thử tách nhỏ biểu thức cần tính:
>$$
>\begin{flalign}
&\;\sum_{i = 1}^n \sum_{j = i}^n \left[ \max \left( A_i, A_{i+1}, \dots, A_j\right) - \min \left( A_i, A_{i+1}, \dots, A_j\right) \right] \\
&= \sum_{i = 1}^n \sum_{j = i}^n \max \left( A_i, A_{i+1}, \dots, A_j\right) - \sum_{i = 1}^n \sum_{j = i}^n \min \left( A_i, A_{i+1}, \dots, A_j\right)
\end{flalign}
>$$
>
>Nghĩa là, ta tính tổng các **số lớn nhất trong các đoạn** và trừ đi tổng các **số nhỏ nhất trong các đoạn**.
>
>:::success
>Nhưng ta vẫn có thể đơn giản hóa bài toán hơn nữa về việc tính biểu thức:
>$$
>\sum_{i=1}^n A_i \cdot \operatorname{mx}_{A_i} - \sum_{i=1}^n A_i \cdot \operatorname{mn}_{A_i}
>$$
>Trong đó:
>- $\operatorname{mx}_{A_i}$ là **số lượng đoạn con chứa $A_i$ nhận $A_i$ là giá trị lớn nhất**.
>- $\operatorname{mn}_{A_i}$ là **số lượng đoạn con chứa $A_i$ nhận $A_i$ là giá trị nhỏ nhất**.

Như vậy, với mỗi số $A_i$, ta cần tìm $\operatorname{mx}_{A_i}$ và $\operatorname{mn}_{A_i}$.

:::info
Sau đây, lời giải sẽ chỉ hướng dẫn việc tính $\operatorname{mx}_{A_i}$, vì tính $\operatorname{mn}_{A_i}$ cũng tương tự.
:::

Nói cách khác, $\operatorname{mx}_{A_i}$ là số lượng đoạn con $[l, r]$ mà $\max \left( A_l, A_{l+1}, \dots, A_r \right) = A_i$ với $l \le i \le r$. Nhận thấy ==$u \le l \le r \le v$== với:
- $u$ là chỉ số nhỏ nhất thỏa $u \lt i$ và $A_u, A_{u+1}, \dots, A_{i-1} \lt A_i$.
- $v$ là chỉ số lớn nhất thỏa $v \gt i$ và $A_{i+1}, A_{i+2}, \dots, A_{v} \lt A_i$

Có thể tìm được hai số $u$ và $v$ này bằng **tìm kiếm nhị phân** kết hợp với **tìm max trên đoạn bằng bảng thưa (sparse table)** hoặc **đi bộ trên cây segment tree**.

Khi này, số lượng đoạn con nhận $A_i$ làm $\max$ là:
$$
\left(i - u + 1 \right)\cdot\left(v-i+1\right)
$$

**Độ phức tạp thời gian:** $O \left( n \log n \right)$.

:::success
:::spoiler Code (Sparse table)

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5, MOD = 1e9+7;

int n, a[N+5], lg2[N+5], tmin[20][N+5], tmax[20][N+5];
long long ans = 0;

void build() {
    for (int i = 1; i <= n; i++) {
        tmin[0][i] = tmax[0][i] = a[i];
    }
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            tmin[j][i] = min(tmin[j-1][i], tmin[j-1][i + (1 << (j-1))]);
            tmax[j][i] = max(tmax[j-1][i], tmax[j-1][i + (1 << (j-1))]);
        }
    }
    for (int i = 2; i <= n; i++) {
        lg2[i] = lg2[i >> 1] + 1;
    }
}

int get_max(int l, int r) {
    int j = lg2[r - l + 1];
    return max(tmax[j][l], tmax[j][r - (1 << j) + 1]);
}

int get_min(int l, int r) {
    int j = lg2[r - l + 1];
    return min(tmin[j][l], tmin[j][r - (1 << j) + 1]);
}

int max_left(int i) {
    int l = 1, r = i, res = i;
    while (l <= r) {
        int m = (l+r)/2;
        if (get_max(m,i) > a[i]) {
            l = m+1;
        }
        else {
            res = m;
            r = m-1;
        }
    }
    return res;
}

int max_right(int i) {
    int l = i, r = n, res = i;
    while (l <= r) {
        int m = (l+r)/2;
        if (get_max(i,m) > a[i]) {
            r = m-1;
        }
        else {
            res = m;
            l = m+1;
        }
    }
    return res;
}

int min_left(int i) {
    int l = 1, r = i, res = i;
    while (l <= r) {
        int m = (l+r)/2;
        if (get_min(m,i) < a[i]) {
            l = m+1;
        }
        else {
            res = m;
            r = m-1;
        }
    }
    return res;
}

int min_right(int i) {
    int l = i, r = n, res = i;
    while (l <= r) {
        int m = (l+r)/2;
        if (get_min(i,m) < a[i]) {
            r = m - 1;
        }
        else {
            res = m;
            l = m + 1;
        }
    }
    return res;
}

main() { 
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    build();
    for (int i = 1; i <= n; i++) {
        ans += 1LL * (max_right(i) - i + 1) * (i - max_left(i) + 1) % MOD * a[i] % MOD;
        ans -= 1LL * (min_right(i) - i + 1) * (i - min_left(i) + 1) % MOD * a[i] % MOD;
    }
    cout << (ans % MOD + MOD) % MOD;
}

:::

### Subtask 3

Kế thừa tư tưởng của subtask trước.

Vì dãy $A$ đã được sắp xếp tăng dần nên dễ dàng nhận thấy:
- $\max$ và $\min$ trong đoạn $[l, r]$ lần lượt là $A_r$ và $A_l$.
- $A_i$ là $\max$ trong các đoạn $[1,i],[2,i],\dots,[i,i]$ (có ==$i$== đoạn).
- $A_i$ là $\min$ trong các đoạn $[i,i],[i,i+1],\dots,[i,n]$ (có ==$n-i+1$== đoạn).

:::success
Như vậy, **đáp án** của bài toán là **biểu thức** sau:
$$
\sum_{i=1}^n A_i \cdot i - \sum_{i=1}^n A_i \cdot (n - i + 1)
$$
:::

**Độ phức tạp thời gian:** $O \left( n \right)$.

:::success
:::spoiler Code

#include<bits/stdc++.h>
using namespace std;

const int MOD = 1e9+7;

int n;
long long sum, ans;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
    	long long a;
    	cin >> a;
    	ans += (a * i - a * (n - i + 1));
        ((ans %= MOD) += MOD) %= MOD;
        //Trong trường hợp ans bị âm cần + MOD
    }
    cout << ans % MOD;
}

:::

### Subtask 4

Kế thừa tư tưởng từ subtask 2. Tuy nhiên, có hai vấn đề cần xử lý:
- Giới hạn dữ liệu lớn.
- $A_i$ không phân biệt.

>[!Tip] Về giới hạn dữ liệu
> Cần thực hiện thao tác tìm $u$ và $v$ bằng kĩ thuật [**monotonic stack**](https://www.youtube.com/watch?v=Dq_ObZwTY_Q) để giảm độ phức của các thao tác từ $O(\log)$ xuống còn $O(1)$.

>[!Tip] Về các giá trị trùng lặp
> Nếu vẫn giữ nguyên thuật toán như trên, sẽ dẫn đến tình trạng ==đếm dư==.
>
> Cụ thể, khi tính $\text{mx}_i$ và $\text{mx}_j$ với ==$A_i = A_j$== cùng là số lớn nhất trong ==một đoạn $[l, r]$==, đoạn đó sẽ vô ý bị xét đến hai lần.
>
> :::success
> Cách xử lý đơn giản nhất ở đây là ==đặt cận== cho $u$ hoặc $v$. Ban đầu, ta có:
>- $u$ là chỉ số nhỏ nhất thỏa $u \lt i$ và $A_u, A_{u+1}, \dots, A_{i-1} \lt A_i$.
>- $v$ là chỉ số lớn nhất thỏa $v \gt i$ và $A_{i+1}, A_{i+2}, \dots, A_{v} \lt A_i$
>
> Ta có thể đặt cận cho $v$ ($v$ không được mở rộng ra đến giá trị bằng $A_i$):
> - $u$ là chỉ số nhỏ nhất thỏa $u \lt i$ và $A_u, A_{u+1}, \dots, A_{i-1} \le A_i$.
> - $v$ là chỉ số lớn nhất thỏa $v \gt i$ và $A_{i+1}, A_{i+2}, \dots, A_{v} \lt A_i$
>
> Hoặc đặt cận cho $u$ ($u$ không được mở rộng ra đến giá trị bằng $A_i$):
> - $u$ là chỉ số nhỏ nhất thỏa $u \lt i$ và $A_u, A_{u+1}, \dots, A_{i-1} \lt A_i$.
> - $v$ là chỉ số lớn nhất thỏa $v \gt i$ và $A_{i+1}, A_{i+2}, \dots, A_{v} \le A_i$
> :::
> Thực hiện ==hoàn toàn tương tự== để tính ==$\text{mn}_i$==.

**Độ phức tạp thời gian:** $O(n)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 2e6, MX = 1e9;
const long long M = 1e9 + 7;
long long n, A[N+2];

long long NLE[N+1], PLS[N+1];
//Next less (or equal) - Previous less (strict)

long long NGE[N+1], PGS[N+1];
//Next greater (or equal) - Previous greater (strict)

stack<long long> sta; 
void clear() {
    while (!sta.empty()) {
        sta.pop();
    }
}

long long add(long long a, long long b) {
    return (a + b) % M;
}

long long sub(long long a, long long b) {
    return ((a - b) % M + M) % M;
}

long long mul(long long a, long long b) {
    return (a * b) % M;
}

main() {
    cin >> n;
    for (long long i = 1; i <= n; i++)
        cin >> A[i];

    //Initialize PLS

    clear();
    A[0] = -(MX + 1);
    sta.push(0);

    for (int i = 1; i <= n; i++) {
        while (A[sta.top()] >= A[i]) {
            sta.pop();
        }

        PLS[i] = sta.top();
        sta.push(i);
    }

    //Initialize NLE

    clear();
    A[n+1] = -(MX + 1);
    sta.push(n+1);

    for (int i = n; i >= 1; i--) {
        while (A[sta.top()] > A[i]) {
            sta.pop();
        }

        NLE[i] = sta.top();
        sta.push(i);
    }

    //Initialize PGS

    clear();
    A[0] = MX + 1;
    sta.push(0);

    for (int i = 1; i <= n; i++) {
        while (A[sta.top()] <= A[i]) {
            sta.pop();
        }

        PGS[i] = sta.top();
        sta.push(i);
    }

    //Initialize NGE

    clear();
    A[n+1] = MX + 1;
    sta.push(n+1);

    for (int i = n; i >= 1; i--) {
        while (A[sta.top()] < A[i]) {
            sta.pop();
        }

        NGE[i] = sta.top();
        sta.push(i);
    }

    //Find total value of MIN OF SUBARRAY
    int totalMn = 0;
    for (int i = 1; i <= n; i++) {
        totalMn = add(totalMn, mul(mul(A[i], (NLE[i] - i)), (i - PLS[i])));
    }

    //Find total value of MAX OF SUBARRAY
    int totalMx = 0;
    for (int i = 1; i <= n; i++) {
        totalMx = add(totalMx, mul(mul(A[i], (NGE[i] - i)), (i - PGS[i])));
    }

    //Result
    cout << sub(totalMx, totalMn);

    return 0;
}

:::

## Bài 4: Trò chơi của John (5 điểm)

### Tóm tắt đề bài:

Cho một bảng trò chơi gồm $n$ hàng và $n$ cột. Ô giao giữa hàng $i$ và cột $j$ có số điểm là $A_{i, j}$.

Tại một ô, người chơi có thể di chuyển đến $4$ ô kề cạnh. Số điểm khi đi từ một ô đến ô khác là số điểm nhỏ nhất trong trong tất cả các ô mà người chơi đi qua.

Trò chơi gồm $q$ màn, mỗi màn chơi cho biết ô xuất phát và ô đích phải đi đến (đảm bảo hai phòng phân biệt).

**Dữ liệu đảm bảo:** $1 \le n \le 400$, $1 \le q \le 3 \cdot 10^5$ và $1 \le A_{i, j} \le 10^9$.

**Yêu cầu:** Hãy tính số điểm lớn nhất có thể nhận được ở mỗi màn chơi.

**Subtask:**
- $50\%$ số điểm: $1 \le n, q \le 100$.
- $50\%$ số điểm: Không có ràng buộc gì thêm.

### Mô hình hóa bài toán:

Cho một đồ thị $n \cdot n$ đỉnh được cho dưới dạng bảng, mỗi đỉnh có cạnh nối đến $4$ đỉnh kề nó trên bảng. Khi đi từ đỉnh này đến đỉnh khác, số điểm người chơi nhận được là số điểm của ô có số điểm nhỏ nhất trên đường đi.

Cho $q$ truy vấn, mỗi truy vấn cho đỉnh xuất phát và đỉnh kết thúc, tìm số điểm lớn nhất người chơi có thể đạt được.

### Subtask 1

>[!Tip] Đánh số lại đồ thị
>Để dễ thực hiện các thao tác trên đồ thị, ta tiến hành ==đánh số== các ô trên bảng:
$$
\text{ID}_{x, y} = (x - 1) \cdot n + y
$$

Áp dụng thuật toán [**Dijkstra**](https://viblo.asia/p/thuat-toan-dijkstra-va-ung-dung-aWj53zgQl6m) suy biến để tìm **đường đi có số điểm lớn nhất** như sau:
- Gọi $\text{max_score}_i$ là số điểm lớn nhất khi xuất phát từ đỉnh đã cho và đến được đỉnh $i$.
- Ưu tiên duyệt đồ thị từ những đỉnh $i$ với $\text{max_score}_i$ lớn nhất, nghĩa là lưu thông tin này trong một cấu trúc dữ liệu sắp xếp tăng dần (priority_queue).

**Độ phức tạp thời gian:** $O \left( n^2 \log n^2 \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 102;
int n, q, a[N][N];
int dx[] = {-1, 1, 0, 0};
int dy[] = { 0, 0, 1,-1};
vector <int> ed[N*N];
int max_score[N*N], w[N*N];

int id(int x, int y) {
    return (x-1)*n + y;
}

void add_edge(int u, int v){
    ed[u].push_back(v);
    ed[v].push_back(u);
}

int dijkstra(int s, int t) {
    memset(max_score, 0, sizeof max_score);
    priority_queue < pair<int, int> > prq;
    max_score[s] = w[s];
    prq.push({max_score[s], s});

    while (prq.size() > 0) {
        int u = prq.top().second, score_u = prq.top().first;
        prq.pop();
        if (score_u < max_score[u]) continue;
        for (int v : ed[u]) {
            if (max_score[v] < min(max_score[u], w[v])) {
                max_score[v] = min(max_score[u], w[v]);
                prq.push({max_score[v], v});
            }
        }
    }

    return max_score[t];
}

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

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 0; k < 4; k++) {
                int u = i+dx[k], v = j+dy[k];
                
                if (u < 1 || u > n || v < 1 || v > n) {
                    continue;
                }
                
                add_edge(id(i, j), id(u, v));
            }
            
            w[id(i, j)] = a[i][j];
        }
    }

    for (int i = 1; i <= q; i++) {
        int x, y, u, v;
        cin >> x >> y >> u >> v;
        cout << dijkstra(id(x, y), id(u, v)) << '\n';
    }

    return 0;
}

:::

### Subtask 2

>[!Tip] Ý tưởng "chìa khóa"
> Ta dựng một **cây khung lớn nhất đặc biệt**, trong bài toán này nghĩa là cây khung với ==cạnh có trọng số nhỏ nhất là lớn nhất== (khác với định nghĩa **cây khung lớn nhất**).
>
> Việc dựng cây khung không khó. Ta sử dụng thuật toán [**DSU - Disjoint Set Union**](https://wiki.vnoi.info/algo/data-structures/disjoint-set-union), sắp xếp lại tất cả các cạnh của đồ thị giảm dần theo trọng số và ưu tiên dùng những cạnh đầu tiên để ghép vào cây khung.
> > Trọng số của cạnh $(u, v)$ trong bài này là $\min(A_u, A_v)$

Khi này, đồ thị đã liên thông, dễ thấy đường đi từ $u$ đến $v$ bất kỳ ==tối ưu== chính là đường đi từ $u$ đến $v$ trên cây khung mình vừa dựng.

Để tìm được **số điểm** của đường đi, ta áp dụng **nhảy nhị phân** giống trong tìm kiếm LCA - tổ tiên chung gần nhất), độ phức tạp của mỗi thao tác là $O(\log n^2)$.

**Độ phức tạp thời gian:** $O \left( n^2 \log n^2 \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 500, M = 1e5, X = __lg(N*N) + 1;
int n, q, A[N+1][N+1], mn[N+1][N+1][X+1], h[N+1][N+1];
pii root, goal, par[N+1][N+1], p[N+1][N+1][X+1];
vector<pii> pos[M+1], adj[N+1][N+1];

const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};

pii acs(pii u) {
    if (par[u.fi][u.se] == u) return u;
    else return par[u.fi][u.se] = acs(par[u.fi][u.se]);
}

void join(pii u, pii v) {
    pii x = acs(u), y = acs(v);
    
    if (x < y) swap(x, y);
    par[y.fi][y.se] = x;
}

bool in(pii u) {
    return (u.fi >= 1 && u.fi <= n && u.se >= 1 && u.se <= n);
}

void dfs(pii u, pii parent) {
    for (pii v : adj[u.fi][u.se])
        if (v != parent) {
            h[v.fi][v.se] = h[u.fi][u.se] + 1;
            p[v.fi][v.se][0] = u;
            mn[v.fi][v.se][0] = min(A[u.fi][u.se], A[u.fi][u.se]);

            dfs(v, u);
        }
}

void init() {
    for (int k = 1; (1 << k) <= n*n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                pii parent = p[i][j][k-1];
                p[i][j][k] = p[parent.fi][parent.se][k-1];
                mn[i][j][k] = min(mn[i][j][k-1], mn[parent.fi][parent.se][k-1]);
            }
}

int get(pii u, pii v) {
    if (h[u.fi][u.se] < h[v.fi][v.se]) swap (u, v);

    int ret = min(A[u.fi][u.se], A[v.fi][v.se]);
    int k = h[u.fi][u.se] - h[v.fi][v.se];
    for (int i = 0; (1 << i) <= k; i++)
        if (k & (1 << i)) {
            ret = min(ret, mn[u.fi][u.se][i]);
            u = p[u.fi][u.se][i];
        }

    if (u == v) return ret;

    k = __lg(h[u.fi][u.se]);
    for (int i = k; i >= 0; i--)
        if (p[u.fi][u.se][i] != p[v.fi][v.se][i]) {
            ret = min(ret, mn[u.fi][u.se][i]);
            ret = min(ret, mn[v.fi][v.se][i]);
            u = p[u.fi][u.se][i];
            v = p[v.fi][v.se][i];
        }

    return min({ret, mn[u.fi][u.se][0],mn[v.fi][v.se][0]});
}

int main() {
    cin >> n >> q;
    vector<pair<int, pair<pii, pii>>> E;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            cin >> A[i][j];
            par[i][j] = {i, j};
        }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            pii u = {i,j};
            for (int k = 0; k < 4; k++) {
                pii v = {u.fi + dx[k], u.se + dy[k]};
                if (in(v))
                    E.push_back({min(A[u.fi][u.se], A[v.fi][v.se]), {u, v}});
            }
        }

    sort(E.begin(), E.end(), greater<pair<int, pair<pii, pii>>>());
    for (auto pr : E) {
        pii u = pr.se.fi, v = pr.se.se;

        if (acs(u) == acs(v)) continue;
        join(u, v);

        adj[u.fi][u.se].push_back(v);
        adj[v.fi][v.se].push_back(u);
    }

    dfs({1, 1}, {0, 0});
    init();

    while (q--) {
        cin >> root.fi >> root.se >> goal.fi >> goal.se;
        cout << get(root, goal) << "\n";
    }

    return 0;
}

:::