# THI THỬ HSG TỈNH K10+11 - 2025 - LẦN I

>[!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 I (đượ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 - 22:30 ngày 02/03/2025
>
>**Bạn đọc có thể nộp và chấm bài** [TẠI ĐÂY](https://chuyentinbrvt.online/contest/algi_mockhsg9lan2_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: Hệ thống năng lượng (4 điểm)

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

Có $n$ trạm năng lượng được đặt trên một đường thẳng, trạm thứ $i$ truyền công suất năng lượng là $A_i$ đến tất cả các điểm nằm trong đoạn $\left[ L_i, R_i \right]$. Tại một điểm bất kỳ trên tuyến đường, mức năng lượng mà nó nhận được chính là tổng công suất của tất cả các trạm đang truyền tải năng lượng qua điểm đó.

**Yêu cầu:** Tìm mức năng lượng cao nhất của một điểm bất kỳ.

**Dữ liệu bảo đảm:** $1 \le n \le 3 \cdot 10^5$, $1 \le A_i \le 10^9$ và $1 \le L_i \le R_i \le 10^9$.

**Subtasks:**

- Subtask 1: $20\%$ số test tương ứng với $1 \le n, L_i, R_i \le 10^3$.
- Subtask 2: $40\%$ số test tương ứng với $1 \le L_i, R_i \le 10^7$.
- Subtask 3: $40\%$ số test tương ứng với $1 \le L_i, R_i \le 10^9$.

### Subtask 1:

Gọi ==$f_x$== là ==mức năng lượng của điểm x==.

Với mỗi trạm năng lượng thứ $i$, ta tăng công suất các điểm $f_{L_i}, f_{L_i+1}, \dots, f_{R_i}$ lên $A_i$.

**Đáp án:** $\max \left( f_1, f_2, \dots, f_{10^3} \right)$

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

:::success
:::spoiler Code

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

const int N = 1000;
int n, L[N + 5], R[N + 5], F[N + 5];
long long A[N + 5];

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

    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = L[i]; j <= R[i]; j++) {
            F[j]++;
            ans = max(ans, F[j]);
        }
    }
    
    cout << ans;
    
    return 0;
}

:::

### Subtask 2:

Nhận thấy, tương ứng với mỗi trạm năng lượng $i$, các giá trị $f_{L_i}, f_{L_i + 1}, \dots, f_{R_i}$ đều tăng thêm $A_i$ đơn vị. Chính vì vậy, có thể áp dụng [**mảng hiệu**](https://wiki.vnoi.info/algo/data-structures/prefix-sum-and-difference-array.md) để thực hiện nhanh thao tác này.

Gọi $D$ là mảng hiệu tương ứng với mảng $f$, trong đó $D_i = A_i - A_{i-1}$

Với mỗi trạm năng lượng $i$, ta tăng đều $f$ trong đoạn $\left[ L_i, R_i \right]$ lên $A_i$ đơn vị bằng cách ==tăng $D_{L_i}$ lên $A_i$ đơn vị== và ==giảm $D_{R_i + 1}$ đi $A_i$ đơn vị==.

>[!Tip]
> Giải thích một cách ngắn gọn, khi tăng đều một đoạn con $\left[ L_i, R_i \right]$, chỉ có hiệu giữa cặp số $\left( L_{i-1}, L_i \right)$ và $\left( R_{i}, R_{i+1} \right)$ là thay đổi.

Sau tất cả các thao tác, ta tính được $f_i = D_1 + D_2 + ... + D_i$.

**Đáp án:** $\max \left( f_1, f_2, \dots, f_{10^7} \right)$.

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

:::success
:::spoiler Code

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

const int N = 1e7;
int n, F[N+2];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        long long l, r, a;
        cin >> l >> r >> a;
        F[l] += a; F[r+1] -= a;
    }
    
    long long ans = 0;
    for (int i = 1; i <= N; i++) {
        F[i] += F[i-1];
        ans = max(ans, F[i]);
    }
    
    cout << ans;
    
    return 0;
}

:::

### Subtask 3:

Vấn đề của subtask này là $L_i, R_i \le 10^9$, đã vượt ngoài phạm vi lưu trữ mảng dẫn đến không thể áp dụng thuật toán của subtask trước.

Có thể áp dụng thuật toán ==đường quét (sweep line)==.

>[!Important] Nhận xét
> Nếu một điểm có tổng mức năng lượng là $x$, luôn tồn tại ít nhất một điểm khác cũng có mức năng lượng là $x$ và là đầu mút của một đường thẳng ứng với trạm bất kỳ.
>
> Như vậy, chỉ cần quan tâm đến hai đầu mút của từng đoạn thẳng ứng với mỗi trạm năng lượng, tức là các vị trí $L_i$ và $R_i$.

Ta thực hiện mô phỏng việc di chuyển từ tọa độ trái nhất sang phải nhất, cùng lúc phải lưu được thông tin về mức năng lượng của điểm đang được xét để lấy kết quả tốt nhất trong các điểm.

Để làm được điều đó, ta thể hiện một vị trí $i$ bằng cặp giá trị $\left( i, energy \right)$, trong đó:
- $i$ là ==vị trí== của điểm.
- $energy$ là sự ==thay đổi về mức năng lượng== khi đi qua điểm này:
- Nếu $i$ là vị trí kết thúc phạm vi truyền năng lượng của trạm thứ $i$, ==$energy = -A_i$==.
- Nếu $i$ là vị trí bắt đầu phạm vi truyền năng lượng của trạm thứ $i$, ==$energy = A_i$==.

Sắp xếp lại danh sách các vị trí trên, ưu tiên ==vị trí $i$ tăng dần== (để đảm bảo việc di chuyển từ trái sang phải), sau đó ưu tiên ==$energy$ giảm dần== (Vì tuy $i$ là kết thúc của phạm vi truyền năng lượng nhưng vẫn được tính vào mức năng lượng chung, nên cần trừ đi các giá trị $energy$ sau cùng).

**Độ 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;
vector<pii> V;

bool cmp(pii a, pii b) {
    if (a.fi == b.fi) {
        return (a.se > b.se);
    }
    else {
        return a.fi < b.fi;
    }
}

int32_t main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int l, r, a;
        cin >> l >> r >> a;
        V.pb({l, a});
        V.pb({r, -a});
    }

    long long res = 0, val = 0;
    sort(all(V), cmp);
    for (auto pr : V) {
        val += pr.se;
        res = max(res, val);
    }

    cout << res;

    return 0;
}

:::

## Bài 2: Đảo cổ đại (5 điểm)

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

Cho một hòn đảo dưới dạng một đa giác không tự cắt, có $n$ đỉnh với các tọa độ nguyên $(x_i, y_i)$, các cạnh song song với trục tọa độ.

**Yêu cầu:** Cho $q$ truy vấn dưới dạng `a b u v`, với mỗi truy vấn cần tìm đường đi ngắn nhất để đi từ điểm $(a, b)$ đến điểm $(u, v)$ mà chỉ được đi men theo biên giới của hòn đảo (tức là cạnh của đa giác).

**Dữ liệu bảo đảm:** $(a, b), (u, v)$ thuộc biên giới của đảo; $1 \le n, q \le 10^5$ và $|x_i|, |y_i| \le 10^3$.

**Subtasks:**

- Subtask 1: $20\%$ số lượng test ứng với $n, q, |x_i| ,|y_i| \le 100$.
- Subtask 2: $20\%$ số lượng test ứng với $n, q \le 10^3$.
- Subtask 3: $60\%$ số lượng test không có ràng buộc gì thêm.

### Subtask 1:

Duyệt qua từng cặp điểm kề nhau trong đa giác và thêm cạnh giữa chúng. Sau đó, ta lập được một đồ thị.

Với mỗi truy vấn `a b u v`, thực hiện BFS từ $(a, b)$ để tìm đường đi ngắn nhất đến $(u, v)$.

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

:::success
:::spoiler Code

#include <bits/stdc++.h>

#define N 1000005
using namespace std;

int n, x[N], y[N], d[N], q, f[201][201];
vector <int> a[N];

int id(int x, int y){
    return x*201 + y;
}

void add(int x, int y, int u, int v){
    f[x][y] = f[u][v] = 1;
    a[id(x, y)].push_back(id(u, v));
    a[id(u, v)].push_back(id(x, y));
}

int main(){
    cin >> n >> q;
    for (int i = 1; i <= n; i++){
        cin >> x[i] >> y[i];
        
        x[i] += 100;
        y[i] += 100;
    }
    
    x[n+1] = x[1];
    y[n+1] = y[1];

    for (int i = 1; i <= n; i++){
        int u = x[i];
        int v = y[i];
        
        while (u < x[i+1]) add(u, v, u+1, v), u++;
        while (u > x[i+1]) add(u, v, u-1, v), u--;
        while (v < y[i+1]) add(u, v, u, v+1), v++;
        while (v > y[i+1]) add(u, v, u, v-1), v--;
    }

    for (int i = 1; i <= q; i++){
        int x, y, u, v;
        cin >> x >> y >> u >> v;
        
        x += 100;
        y += 100;
        u += 100;
        v += 100;
        
        memset(d, 0, sizeof d);
        
        queue <int> q;
        q.push(id(x, y));
        d[id(x, y)] = 1;
        
        while (q.size()){
            int u = q.front();
            q.pop();
            
            for (int v : a[u])  {
                if (d[v] == 0) {
                    d[v] = d[u]+1;
                    q.push(v);
                }
            }
        }
        
        cout << d[id(u, v)] - 1 << '\n';
    }

    return 0;
}

:::

### Subtask 2:

Cần chú ý, trong trường hợp hòn đảo có hình dáng ==**zig-zag**==, biên giới của hòn đảo sẽ có độ dài lớn, cận kề giá trị tối đa của kích thước hòn đảo là $10^6$.

Chính vì vậy, cần cải tiến bước tìm đường đi ở **subtask 1**.

Có thể thực hiện ==nhảy qua các cạnh== thay vì ==đi qua tất cả các điểm trên cạnh==. Bằng cách này, ta dễ dàng xác định khi nào đã tới vị trí cần tìm.

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

:::success
:::spoiler Code

#include <bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define fi first
#define se second

using namespace std;
const int N = 2000;
int n, q, cnt, ans;
int x[N+5], y[N+5];
ii f[N+5][N+5];

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

bool out(int u, int v) {
    return (u < 0 || u > 2000 || v < 0 || v > 2000);
}

void calc(int x, int y, int fix, int fiy) {
    if (x == fix && ((f[x][y].se >= fiy && fiy >= y) || (f[x][y].se <= fiy && fiy <= y))) {
        ans = min(ans, cnt + abs(fiy-y));
        return;
    }
    
    if (y == fiy && ((f[x][y].fi >= fix && fix >= x) || (f[x][y].fi <= fix && fix <= x))){
        ans = min(ans, cnt + abs(fix-x));
        return;
    }
    
    cnt += abs(f[x][y].fi-x) + abs(f[x][y].se-y);
    calc(f[x][y].fi, f[x][y].se, fix,fiy);
    cnt -= abs(f[x][y].fi-x) + abs(f[x][y].se-y);
}
void join1(int &u, int v, int x, int y, int w) {
    f[u][v] = ii(x, y);
    u += w;
}

void join2(int u, int &v, int x, int y, int w) {
    f[u][v] = ii(x, y);
    v += w;
}

void solve() {
    cin >> n >> q >> x[1] >> y[1];
    x[1] += 1e3;
    y[1] += 1e3;
    
    for (int i = 2; i <= n; i++){
        cin >> x[i] >> y[i];
        x[i] += 1e3;
        y[i] += 1e3;
        int u = x[i-1], v = y[i-1];
        while (u < x[i]) join1(u, v, x[i], y[i], 1);
        while (u > x[i]) join1(u, v, x[i], y[i], -1);
        while (v < y[i]) join2(u, v, x[i], y[i], 1);
        while (v > y[i]) join2(u, v, x[i], y[i], -1);
    }

    int u = x[n], v = y[n];
    while (u < x[1]) join1(u, v, x[1], y[1], 1);
    while (u > x[1]) join1(u, v, x[1], y[1], -1);
    while (v < y[1]) join2(u, v, x[1], y[1], 1);
    while (v > y[1]) join2(u, v, x[1], y[1], -1);

    while (q--) {
        int x, y, u, v;
        cin >> x >> y >> u >> v;
        
        x += 1e3;
        y += 1e3;
        u += 1e3;
        v += 1e3;
        cnt = 0, ans = 1e18;
        
        calc(x, y, u, v);
        calc(u, v, x, y);
        
        cout << ans << '\n';
    }
}
main() {
    solve();
    return 0;
}

:::

### Subtask 3:

Với ràng buộc dữ liệu ở **subtask** này, dễ thấy việc di chuyển theo các cạnh thay vì các định vẫn chưa đủ nhanh.

Nếu ==duỗi thẳng biên giới của hòn đảo và coi đó là một đoạn thẳng==, đánh số các điểm bắt đầu từ $1$, có thể thấy khoảng cách giữa hai điểm $i$ và $j$ $\left( i \lt j \right)$ có thể là:
- $j - i$.
- $len - (j - i + 1)$ với $len$ là tổng số lượng điểm năm trên biên giới của đảo.

tương ứng với hai hướng đi xuất phát ngược nhau. Đáp án của mỗi truy vẫn là giá trị nhỏ nhất trong hai giá trị trên.

**Độ phức tạp thời gian:** $O \left(S \right)$ với $S$ là chu vi tối đa của hòn đảo (khoảng $10^6$).

:::success
:::spoiler Code

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

const int N = 2e5, V = 1e3;
int q, n, S[2*V+5][2*V+5];
pii A[N+1];

int main() {
    cin >> q >> n;
    for (int i = 1; i <= n; i++) {
        cin >> A[i].fi >> A[i].se;
        A[i].fi += V + 1;
        A[i].se += V + 1;
    }
    
    n++;
    A[n] = A[1];
    S[A[1].fi][A[1].se] = 1;
    for (int i = 2; i <= n; i++) {
        if (A[i].fi == A[i-1].fi) {
            if (A[i].se > A[i-1].se) {
                for (int j = A[i-1].se + 1; j <= A[i].se; j++) {
                    S[A[i].fi][j] = S[A[i].fi][j-1] + 1;
                }
            } else {
                for (int j = A[i-1].se - 1; j >= A[i].se; j--) {
                    S[A[i].fi][j] = S[A[i].fi][j+1] + 1;
                }
            }
        } else {
            if (A[i].fi > A[i-1].fi) {
                for (int j = A[i-1].fi + 1; j <= A[i].fi; j++) {
                    S[j][A[i].se] = S[j-1][A[i].se] + 1;
                }
            } else {
                for (int j = A[i-1].fi - 1; j >= A[i].fi; j--) {
                    S[j][A[i].se] = S[j+1][A[i].se] + 1;
                }
            }
        }
    }

    int mx = S[A[1].fi][A[1].se];
    S[A[1].fi][A[1].se] = 1;
    
    while (q--) {
        int x, y, u, v;
        cin >> x >> y >> u >> v;
        x += V + 1; y += V + 1; u += V + 1; v += V + 1;

        int l = min(S[u][v], S[x][y]), r = max(S[u][v], S[x][y]);
        int dist = min(r - l, mx - r + l - 1);
        cout << dist << "\n";
    }

    return 0;
}

:::

## Bài 3: Chia bánh (6 điểm)

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

Tèo có một chiếc bánh kem gồm $n$ miếng có độ ngon lần lượt là $A_1, A_2, \cdots, A_n$.

Tèo cần chia $n$ miếng bánh trên thành $m+1$ phần liên tiếp nhau (cho chính mình một phần và cho $m$ người bạn mỗi người một phần) thỏa mãn:
- Phần bánh của mỗi người bạn đều có tổng độ ngon không nhỏ hơn $k$.
- Phần bánh của mình có tổng độ ngon là lớn nhất có thể.

**Mô hình hóa bài toán:** Cho ba số nguyên $n, m, k$ và dãy $n$ số nguyên dương $A_1, A_2, \dots, A_n$

**Yêu cầu:** Chia dãy số thành $m+1$ phần gồm các phần tử liên tiếp nhau (có thể có phần tử rỗng) sao cho trong đó có ==$m$ phần có tổng không nhỏ hơn $k$== và ==tổng của phần còn lại là lớn nhất==.

**Subtasks:**
- $15\%$ số điểm: $1 \le m \le n \le 15$.
- $15\%$ số điểm: $700 \le m \le n \le 10^3$.
- $30\%$ số điểm: $2 \cdot 10^5 \le m \le n \le 3 \cdot 10^5$.
- $40\%$ số điểm: $10^6 \le m \le n \le 2 \cdot 10^6$.

### Subtask 1:

Dùng kĩ thuật quay lui để sinh ra mọi cách chia $n$ phần tử thành $m+1$ phần.

Kiểm tra nếu trong đó có ít nhất $m$ phần có tổng không nhỏ hơn $k$ thì cập nhật đáp án.

**Độ phức tạp thời gian:** $O \left(n \log n \cdot C_{n+m}^{m} \right)$
>[!Note]Trong đó:
>- Với mỗi cách chia, ta cần sort trong $O(n \log n)$, để kiểm tra và cập nhật đáp án.
>- Ta có $C_{n+m}^{m}$ cách chia $n$ miếng bánh thành $m+1$ phần, cách tính dựa trên bài toán **[chia kẹo Euler](https://viblo.asia/p/bai-toan-chia-keo-euler-L4x5xqvqKBM)**.

:::success
:::spoiler Code

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

const int N = 16;
int n, m, k, a[N], res = -1;

int pos[N];
//Pos[i] là nhóm của miếng bánh thứ i

int sum[N];
//Sum[i] là tổng độ ngon của nhóm thứ i

void Try(int x) {
    if (x > n){
        for (int i = 1; i <= m+1; i++) {
            sum[i] = 0;
        }
        
        for (int i = 1; i <= n; i++) {
            sum[pos[i]] += a[i];
        }
        
        sort(sum+1, sum + 1 + m + 1);

        //Không đủ m nhóm có tổng >= k
        if (sum[2] < k) {
            return;
        }

        //Có đúng m nhóm có tổng >= k
        if (sum[1] < k) {
            res = max(res, sum[1]);
        }

        //Tất cả nhóm đều có tổng >= k
        if (sum[1] >= k) {
            res = max(res, sum[m+1]);
        }
        
        return;
    }
    
    for (int i = pos[x-1]; i <= m+1; i++){
        pos[x] = i;
        Try(x + 1);
    }
}

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

    pos[0] = 1;
    Try(1);
    cout << res;

    return 0;
}

:::

### Subtask 2:

>[!Important] **Nhận xét quan trọng**
> Nếu chọn đoạn $\left[i, j \right]$ làm phần bánh của Tèo thì cần thỏa mãn
> - Đoạn $\left[1, i-1 \right]$ chia được thành nhiều nhất $x$ phần có tổng không nhỏ hơn $k$.
> - Đoạn $\left[j+1, n \right]$ chia được thành nhiều nhất $y$ phần có tổng không nhỏ hơn $k$.
> - ==$x + y \ge m$==.

>[!Tip] Gọi:
> - $\operatorname{pre} \left[i \right]$ là số nhóm nhiều nhất chia được từ các phần tử của đoạn $\left[1, i \right]$
> - $\operatorname{suf} \left[ i \right]$ là số nhóm nhiều nhất chia được từ các phần tử của đoạn $\left[i, n \right]$.

Vậy đáp án chính là tổng của đoạn con $\left[i, j \right]$ dài nhất thỏa $pre \left[i-1 \right] + suf \left[j+1 \right] \ge m$.

Xây dựng trước mảng $\operatorname{pre}, \operatorname{suf}$ như sau:
- $\operatorname{pre}_i = \max \left( \operatorname{pre}_j \right) + 1$ với $j \lt i$ thỏa mãn $A_i + A_{i-1} + \dots + A_{j+1} \ge k$
- $\operatorname{suf}_i = \max \left( \operatorname{suf}_j \right) + 1$ với $j \gt i$ thỏa mãn $A_i + A_{i+1} + \dots + A_{j-1} \ge k$

Nghĩa là với mỗi vị trí $i$, duyệt qua mọi vị trí $j$ trước nó, nếu $A_i + A_{i-1} + \dots + A_{j+1} \ge k$, ta lấy $\max$ của $\operatorname{pre}_i$ với $\operatorname{pre}_j + 1$. Ngược lại với $\operatorname{suf}_i$.

Cuối cũng, thử đặt từng đoạn con $\left[ i, j \right]$ làm **phần bánh cho Tèo**, dễ dàng kiểm tra xem cách lấy này có hợp lệ hay không bằng cách kiểm tra biểu thức sau:
$$
\operatorname{pre}_{i-1} + \operatorname{suf}_{j+1} \ge m
$$
> Biểu thức trên kiểm tra xem tổng số phần bánh thỏa mãn tạo được sau khi đã lấy đi phần bánh của Tèo có đủ cho $m$ người bạn của Tèo hay không.

Để tìm đáp án tối ưu, ta lấy $\max$ kết quả với tổng của đoạn $\left[i, j \right]$ (có thể tính nhanh bằng ==tổng cộng dồn - prefix sum==).

**Độ 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 = 1001;
int n, m, k, a[N], pre[N], suf[N], s[N];
int res = -1;

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

    pre[0] = 0;
    for (int i = 1; i <= n; i++) {
        int sum = 0;
        pre[i] = 0;
        for (int j = i; j >= 1; j--) {
            sum += a[j];
            if (sum >= k) {
                pre[i] = pre[j-1] + 1;
                break;
            }
        }
    }

    suf[n+1] = 0;
    for (int i = n; i >= 1; i--) {
        int sum = 0;
        suf[i] = 0;
        for (int j = i; j <= n; j++) {
            sum += a[j];
            if (sum >= k) {
                suf[i] = suf[j+1] + 1;
                break;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            if (pre[i-1] + suf[j+1] == m) {
                res = max(res, s[j] - s[i-1]);
            }
        }
    }

    cout << res;

    return 0;
}

:::

### Subtask 3:

>[!Important] Nhận xét
> Trong bài toán này, có thể áp dụng ==tư tưởng tham lam== đúng đắn trong việc tính mảng $\operatorname{pre}$ và $\operatorname{suf}$ như sau:
> - $\operatorname{pre}_i = \operatorname{pre}_j + 1$ với $j \lt i$ ==gần nhất== thỏa mãn $A_i + A_{i-1} + \dots + A_{j+1} \ge k$
> - $\operatorname{suf}_i = \operatorname{suf}_j + 1$ với $j \gt i$ ==gần nhất== thỏa mãn $A_i + A_{i+1} + \dots + A_{j-1} \ge k$
>
> Nhận xét trên đúng vì việc kéo dài phần bánh kết thúc tại $i$ ra nhiều hơn nữa khi đã đạt đủ độ ngon $k$ là không tối ưu, thay vào đó, có thể dùng miếng bánh đó để tối ưu cho phần bánh trước đó.

Như vậy, với mỗi vị trí $i$, có thể dùng ==tìm kiếm nhị phân== và ==tổng cộng dồn== để tính nhanh $\operatorname{pre}_i$ và $\operatorname{suf}_i$.

Đồng thời, sau đó ta cũng áp dụng tư tưởng trên trong việc tìm phần bánh $\left[ i, j \right]$ tối ưu cho Tèo. Cụ thể như sau:
- Cố định $i$, ta biết được đã có $\operatorname{pre}_{i-1}$ phần bánh với độ ngon ít nhất bằng $k$.
- Còn thiếu $m - \operatorname{pref}_{i-1}$ phần bánh có độ ngon ít nhất bằng $k$. Cần tìm $j \ge i$ ==xa nhất== thỏa mãn $\operatorname{suf}_{j+1} \ge m - \operatorname{pref}_{i-1}$.

Đến đây, ta tiếp tục sử dụng ==tìm kiếm nhị phân==.

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

:::success
:::spoiler Code

:::

### Subtask 4:

Nhìn vào sự thay đổi của ràng buộc từ $n \le 3 \cdot 10^5$ sang $n \le 2 \cdot 10^6$, dễ thấy ý đồ của tác giả đang yêu cầu thí sinh phải ==khử $\log$== trong độ phức tạp thuật toán của mình.

Để khử được $\log$ của ==tìm kiếm nhị phân==, người ta nghĩ đến **[kỹ thuật hai con trỏ](https://wiki.vnoi.info/algo/basic/two-pointers)**.

Đây cũng là bước cải tiến cuối cùng để hoàn thành bài toán.

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

:::success
:::spoiler Code

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

const int N = 2e6 + 5;
int n, m, k, suf[N], pre[N], a[N];
long long s[N], res = -1;

long long sum(int l, int r){
    return 0ll + s[r] - s[l-1];
}

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

    int j = 0;
    for (int i = 1; i <= n; i++) {
        pre[i] = 0;
        while (j < i && sum(j+1, i) >= k) j++;
        if (j) {
            pre[i] = pre[j-1] + 1;
        }
    }

    j = n+1;
    for (int i = n; i >= 1; i--) {
        suf[i] = 0;
        while (j > i && sum(i, j-1) >= k) j--;
        if (j <= n) {
            suf[i] = suf[j+1] + 1;
        }
    }

    j = 1;
    for (int i = 1; i <= n; i++){
        while (j < n && pre[i-1] + suf[j+2] >= m) j++;
        if (pre[i-1] + suf[j+1] == m) {
            res = max(res, sum(i, j));
        }
    }

    cout << res;

    return 0;
}

:::

## Bài 4: Phát sóng (5 điểm)

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

Một thành phố có dạng một ma trận, với các ngôi nhà được quy hoạnh thành bảng gồm $n$ hàng và $m$ cột. Vị trí giao giữa hàng $i$ và cột $j$ gọi là $(i, j)$.

Thành phố sẽ lần lượt lắp đặt $q$ trạm phát sóng với phạm vi phát sóng khác nhau. Nếu một trạm được đặt tại vị trí $(x, y)$ và có bán kính phát sóng là $k$, trạm đó có thể phủ sóng cho các ngôi nhà ở vị trí $(u, v)$ với:

$$
|x - u| + |y - v| \le k
$$

**Yêu cầu:** Sau mỗi lần lắp đặt trạm phát sóng, tính toán ==số ngôi nhà đã được phủ sóng==.

**Subtask**:
- 30% test tương ứng với $1 \le q \le 100$.
- 30% test tương ứng với $1 \le k \le 10$.
- 40% test không có ràng buộc gì thêm.

### Subtask 1:

Với mỗi truy vấn, ==duyệt toàn bộ ma trận==, nếu ô nằm trong phạm vi được phát sóng hay không, thực hiện thao tác như sau:
- Nếu ô ==đã được đánh dấu== (đã duyệt qua trước đó) thì bỏ qua.
- Nếu ô ==chưa được đánh dấu== (chưa duyệt qua trước đó):
- Đánh dấu ô là đã duyệt qua.
- Tăng kết quả lên $1$.

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

:::success
:::spoiler Code

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

const int N=10;
int n,m,k,q;
bool a[N+5][N+5];

int main() {
    cin >> n >> m >> k >> q;
    int cnt = 0;
    while (q--){
        int x, y;
        cin >> x >> y;
        
        for (int i = 1; i <= n; i++){
            for (int j = 1; j<=m; j++){
                if (abs(x-i) + abs(y-j) <= k && a[i][j] == 0){
                    a[i][j] = 1;
                    cnt++;
                }
            }
        }
        
        cout << cnt << '\n';
    }

    return 0;
}

:::

### Subtask 2:

Với mỗi truy vấn, ta nhận thấy việc duyệt toàn bộ ma trận là không cần thiết khi các ô chịu ảnh hưởng của truy vấn chỉ nằm trong phạm vi bán kính là $k$.

Do đó, ta thực hiện loang (bằng [**BFS**](https://wiki.vnoi.info/algo/graph-theory/breadth-first-search.md)) từ ô $(x,y)$ ra xung quanh đến khi vượt ra khỏi phạm vi phát sóng thì dừng lại.
>[!Tip] Cách khác
> Hoặc cũng có thể sử dụng hai vòng lặp để duyệt các ô theo hình thoi:
> - Vòng lặp đầu tiên duyệt từ hàng $x - k$ đến $x + k$.
> - Ứng với mỗi hàng, duyệt cột từ $y - \left( k - \left | x - i \right | \right)$ đến $y + \left( k - \left | x - i \right | \right)$.

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

:::success
:::spoiler Code (BFS)

:::

:::success
:::spoiler Code (Duyệt)

#include <bits/stdc++.h>
using namespace std;
const int N=1000;
int n, m, q, cnt;
bool a[N+5][N+5];

int main() {
    cin >> n >> m >> q;
    while (q--){
        int x, y, k;
        cin >> x >> y >> k;
        
        for (int i = max(1, x - k); i <= min(n, x + k); i++)
        	for (int j = max(1, y - (k - abs(x - i))); j <= min(m, y + (k - abs(x - i))); j++) {
        		if (!a[i][j]) cnt++;
        		a[i][j] = 1;
        	}

        cout << cnt << '\n';
    }

    return 0;
}

:::

### Subtask 3:

Giả sử, ta loang lần đầu bạn tiên từ vị trí $(x,y)$ như hình dưới. Khi loang lần tiếp theo ở vị trí $(x',y')$ thì có thể thấy thấy phần bị tô xanh đã bị đi qua hai lần.

Như vậy, ta có nhận xét tạm thời: ==không nên loang đến các vị trí đã được duyệt trước đó==.


Tuy nhiên, ở một trường hợp khác như hình dưới, ta loang lần đầu tiên tại vị trí $(x,y)$ và lần tiếp theo tại vị trí $(x',y')$.

Nếu tuân theo nhận xét phía trên, ở lần loang thứ hai chương trình sẽ ==dừng lại trước khi tới được vùng màu xanh==, trong khi phần màu xanh chưa hề được loang đến.


>[!Important]
> Sau hai trường hợp trên, ta nhận thấy ==tư tưởng tham lam== là không duyệt những ô đã được thăm trước đó là **sai**.

Như vậy, trạng thái với mỗi ô $(i,j)$ không chỉ là **đã thăm** hay **chưa thăm**. Ta cần lưu $d_{i,j}$ là số bước nhiều nhất có thể đi được thêm khi xuất phát tại $(i,j)$. Khi đó, nếu ta loang từ ô $(i,j)$, ta chỉ loang đến ô $(u,v)$ kề nó nếu ==$d_{u,v} \lt d_{i,j} - \left(|i-u|+|j-v|\right)$==.

>[!Tip] Giải thích
> Trong trường hợp $d_{u,v} \ge d_{i,j} - \left(|i-u|+|j-v|\right)$, vào một lần loang bất kỳ trước đó, đảm bảo ==luôn đi được nhiều hơn hoặc bằng== so với khi ta loang hiện tại. Vì vậy, không có lí do nào phải tiếp tục loang thêm một lần nữa.

**Độ phức tạp thời gian:** $O(n \cdot m \cdot k)$.
> Vì mỗi ô $(i,j)$ chỉ có $k$ trạng thái, mỗi trạng thái chỉ được đi qua tối đa một lần.

:::success
:::spoiler Code

#include <bits/stdc++.h>
#define ii pair<int,int>
#define fi first
#define se second

using namespace std;
const int N = 500;

int n, m, q, cnt;
int d[N+5][N+5];
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
bool vis[N+5][N+5];

bool out(int u, int v) {
    return (u < 1 || u > n || v < 1 || v > m);
}

void bfs(int x, int y, int k) {
    if (d[x][y] >= k+1) {
        return;
    }
    
    d[x][y] = k+1;
    queue<ii> q;
    q.push({x,y});

    while (!q.empty()) {
        int u = q.front().fi;
        int v = q.front().se;
        q.pop();
        
        if (vis[u][v] == false) {
            cnt++;
            vis[u][v] = true;
        }

        for(int i = 0; i < 4; i++){
            int nxt_u = u + dx[i];
            int nxt_v = v + dy[i];
            if (out(nxt_u,nxt_v) || d[nxt_u][nxt_v] >= d[u][v] - (abs(u-nxt_u) + abs(v-nxt_v))) {
                continue;
            }
            
            d[nxt_u][nxt_v] = d[u][v] - (abs(u-nxt_u) + abs(v-nxt_v));
            q.push({nxt_u,nxt_v});
        }
    }
}

int main() {
    cin >> n >> m >> q;
    cnt = 0;

    while (q--) {
        int x, y, k;
        cin >> x >> y >> k;

        bfs(x, y, k);

        cout << cnt << '\n';
    }
        
    return 0;
}

:::