# HSG lớp 9 TPHCM năm 2024 - 2025

[toc]

## Bài 1: Sắp xếp (7 điểm)

### Subtask 1:

Ở subtask này ta có $n \le 1000$, dùng thuật toán ==buble sort== như đề bài mô tả và đếm số thao tác đã thực hiện, làm như sau:

- Duyệt qua mọi cặp phần tử kề nhau $a_i$ và $a_{i+1}$, đổi chỗ 2 phần tử này cho nhau và tăng số lần hoán đổi lên nếu $a_i \gt a_{i+1}$.
- Lặp lại quá trình trên đến khi không còn thực hiện được nữa.

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

### subtask 2:

>[!Note]Nhận xét:
>Chắc chắn tồn tại thao tác đổi chỗ hai phần tử $a_i$ và $a_j (i \lt j)$ nếu $a_i \gt a_j$.
>Đáp án bài toán bây giờ chuyển thành đếm số cặp $i, j$ thỏa mãn $i < j$ và $a_i \gt a_j$.

>[!Tip]thuật toán:
>- Sử dụng cấu trúc dữ liệu ==segment tree== hoặc ==fenwick tree==.

**Cách làm:**
Xử lí bài toán offline, mỗi phần tử lưu dưới dạng $pair$ (lưu giá trị và chỉ số), $sort$ các phần tử lại theo thứ tự tăng dần của giá trị, nếu giá trị bằng nhau thì $sort$ tăng dần theo chỉ số.

$\rightarrow$ như vậy, nếu duyệt các phần tử theo thứ tự từ $1$ đến $n$, muốn biết được phần tử $a_i$ lớn hơn bao nhiêu phần tử $a_j (i \le j)$, đáp án chính là số lượng phần tử có chỉ số lớn hơn chỉ số của $a_i$ mà đã duyệt qua trước đó (vì chắc chắn giá trị của $a_i$ là lớn nhất cho đến hiện tại).
$\rightarrow$ ta có thể lưu và lấy giá trị đó bằng 1 trong 2 cấu trúc dữ liệu nói trên.

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

:::success
:::spoiler Code

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

using namespace std;

const int Mod = 1e9 + 7;
const int   N = 2e5 + 5;

int n;
pii a[N];
int t[N];

void up(int x){
    while (x){
        t[x]++;
        x -= x & -x;
    }
}
int get(int x){
    int res = 0;
    while (x <= n){
        res += t[x];
        x += x & -x;
    }
    return res;
}

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
        freopen("SAPXEP.inp","r",stdin);
        freopen("SAPXEP.out","w",stdout);

    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i].fi; a[i].se = i;
    }
    sort(a+1, a+1+n);

    long long res = 0;
    for (int i = 1; i <= n; i++){
        res += get(a[i].se + 1);
        up(a[i].se);
    }
    cout << res;

    return 0;
}

:::

## Bài 2: Khu vực (6.5 điểm)

### subtask 1 và subtask 2:

>[!Note]Nhận xét:
>- được phép đổi 1 thẻ thành số bất kì, điều đó có nghĩa là số cần tìm phải là ước của ít nhất $n-1$ số trong dãy.
>- Hay nói cách khác, đáp án là ==ước chung lớn nhất== của $n-1$ phần tử bất kì trong dãy.

>[!Tip] Tính chất
> $gcd(a, b, c) = gcd(gcd(a, b), c)$

Thứ cần tính bây giờ là $gcd$ của $n-1$ phần tử bất kì, nghĩa là sẽ có 1 phần tử không cần xét. Ta có thể duyệt qua mọi phần tử không cần xét đó, rồi lấy $gcd$ những phần tử còn lại.

**Độ phức tạp thời gian** $O (n \log)$
>trong đó $\log$ là độ phức tạp của $\gcd$.

### subtask 3:

>[!Tip]Cải tiến:
>Sử dụng tư tưởng preffix và suffix, gọi $pre_i$ là $gcd(a_1, a_2, \cdots, a_i)$ và $suf_i$ là $gcd(a_i, a_{i+1}, \cdots, a_{n-1}, a_n)$.

$\rightarrow$ nếu chọn không tính phần tử thứ $i$ thì gcd của $n-1$ phần tử còn lại là $gcd(pre_{i-1}, suf{i+1})$.

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

:::success
:::spoiler Code

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()

using namespace std;

const int Mod = 1e9 + 7;
const int   N = 1e5 + 5;

int n, a[N], pre[N], suf[N];

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
        freopen("KHUVUC.inp","r",stdin);
        freopen("KHUVUC.out","w",stdout);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++) pre[i] = __gcd(pre[i-1], a[i]);
    for (int i = n; i >= 1; i--) suf[i] = __gcd(suf[i+1], a[i]);

    int res = 0;
    for (int i = 1; i <= n; i++)
        res = max(res, __gcd(pre[i-1], suf[i+1]));

    cout << res;

    return 0;
}

:::

## Bài 3: Giải đấu (6.5 điểm)

### subtask 1:

với mỗi truy vấn $l, r$ ta duyệt qua các vị trí $i$ $(l \le i \le r)$, chia các phần tử từ $l$ đến $i$ cho đội thứ nhất, các phần tử từ $i+1$ đến $r$ cho đội thứ 2.
Tính tổng ranking mỗi đội và lấy chệnh lệch nhỏ nhất.

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

### subtask 2:

thuật toán giống như subtask 1, cải tiến phần lấy tổng mỗi đội bằng ==preffix sum==.

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

### subtask 3:

>[!Note]Nhận xét:
>Gọi $sum$ là tổng ranking các phần tử từ $l$ đến $r$.
>Chênh lệch tổng của 2 đội là nhỏ nhất chỉ khi tổng của mỗi đội gần với $sum / 2$ nhất.

Dùng ==tìm kiếm nhị phân== để tìm ra vị trí $pos$ tối ưu mà tại đó, ta chia các phần tử từ $l$ đến $pos$ cho đội thứ nhất và các phần từ tử $pos+1$ đến $r$ cho đội thứ hai.

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

:::success
:::spoiler Code

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int Mod = 1e9 + 7;
const int   N = 1e6 + 5;

int n, q, sum[N];

int getPos(int i, int l, int r, int sumRange){
    int aim = sumRange / 2, pos;
    while (l <= r){
        int m = l+r >> 1;
        if (sum[m] - sum[i-1] >= aim) pos = m, r = m-1;
        else l = m+1;
    }
    return pos;
}

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
        freopen("GIAIDAU.inp","r",stdin);
        freopen("GIAIDAU.out","w",stdout);

    cin >> n >> q;
    for (int i = 1; i <= n; i++){
        int x; cin >> x;
        sum[i] = sum[i-1] + x;
    }

    while (q--){
        int l, r; cin >> l >> r;
        int sumRange = sum[r] - sum[l-1];
        int pos = getPos(l, l, r, sumRange);

        int sumL = sum[pos] - sum[l-1], sumR = sum[r] - sum[pos];
        int res = abs(sumL - sumR);
        pos--;
        sumL = sum[pos] - sum[l-1], sumR = sum[r] - sum[pos];
        res = min(res, abs(sumL - sumR));

        cout << res << '\n';
    }

    return 0;
}

:::