# Solution #3: Đề thi HSG9 TP.HCM (2024-2025)
**Tác giả: Phan Thành Hưng (hungg_261)**
___
:::success
Một số link chấm đề:
- [oj.giftedbat.edu.vn/...](https://oj.giftedbat.edu.vn/contest/hsg9_hcm2025)
- [dethi.nguyenphong.me/...](https://dethi.nguyenphong.me/contest/hsg_hcm_2024)
- [hongbangoj.ucode.vn/...](https://hongbangoj.ucode.vn/contests/hoc-sinh-gioi-tphcm-nam-hoc-2024-2025-67248)
:::
:::warning
Đề được sử dụng trong bài viết này được trích từ: TGBOJ - [oj.giftedbat.edu.vn/...](https://oj.giftedbat.edu.vn/contest/hsg9_hcm2025)
:::
___
## Bài 1 (SAPXEP.*)
### Đề bài
Cho một dãy $a$ gồm $n$ phần tử. Hãy đếm số lần hoán đổi vị trí các phần tử theo thuật toán sắp xếp nổi bọt (Bubble Sort) để sắp xếp dãy không giảm.
>Thuật toán sắp xếp nổi bọt (Bubble Sort) có thể được biểu diễn thông qua đoạn pseudo-code (mã giả) dưới đây để sắp xếp dãy $a$ gồm $n$ phần tử theo thứ tự không giảm:
> ```
> for i = 1 to n:
> for j = 1 to n-1:
> if a[j] > a[j+1]:
> swap(a[j], a[j+1])
>
> ```
**Ràng buộc:**
- Subtask $1$: $80\%$ số điểm bài thi có $n \le 10^3$.
- Subtask $2$: $20\%$ số điểm bài thi có $n \le 2\cdot10^5$.
___
### Lời giải
#### Subtask 1
Để giải quyết subtask 1 thì rất đơn giản, ta chỉ cần cài theo như mã giả ở trên là được.
:::spoiler **Code**
```cpp=
#include <bits/stdc++.h>
using namespace std;
// hàm sắp xếp nổi bọt (bubble sort)
int bubbleSort(vector<int>& arr) {
int n = arr.size();
long long ans=0;
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
if (arr[j] > arr[j+1]){
swap(arr[j],arr[j+1]);
++ans;
}
}
}
return ans;
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
int n;
cin>>n;
vector<int> arr(n);
for(int i=0;i<n;++i){
cin>>arr[i];
}
cout<<bubbleSort(arr)<<'\n';
return 0;
}
```
##### Đánh giá độ phức tạp
- Độ phức tạp thời gian: $O(n^2)$
- Độ phức tạp không gian: $O(n)$
:::
#### Subtask 2
>[!Tip] **Cách 1**
> **Ý tưởng chính:** ==Merge sort==
Nhận thấy rằng khi sắp xếp xong thì các phần tử được sắp xếp tăng dần, nghĩa là nếu ta đang ở vị trí $i$ thì trong các phần tử $a_{i+1},a_{i+2},…,a_n$, các phần tử mà bé hơn $a_i$ sẽ được đưa lên trước sau khi sắp xếp $\Rightarrow$ chắc chắn đã có sự hoán đổi giữa $a_i$ và các phần tử đó. Vậy là với mỗi $a_i$ ta chỉ cần đếm xem có bao nhiêu vị trí $j$ thỏa mãn $a_i>a_j$ và $i<j \le n$. Thao tác đếm các cặp như vậy tương đương với việc giả sử phần tử ta đang xét hiện tại là $a_i$, thì ta sẽ đếm xem có bao nhiêu $i$ thỏa mãn $a_i<a_j$ và $1 \le j<i$. Chắc hẳn đến đây các bạn cũng nhận ra được đây chính là bài [đếm số cặp nghịch thế](https://oj.vnoi.info/problem/nkinv) kinh điển rồi. Ta có thể biến đổi thuật toán **[Sắp xếp trộn](https://vi.wikipedia.org/wiki/S%E1%BA%AFp_x%E1%BA%BFp_tr%E1%BB%99n) (aka. Merge Sort)** để đếm số cặp nghịch thế ở thao tác trộn (merge).
Ở thuật toán Sắp xếp trộn, ta sẽ biến đổi một chút ở hàm `merge(...)`. Lúc này hàm `merge(...) -> int` sẽ trả ra số cặp nghịch thế. Ta biết rằng thuật toán sắp xếp trộn sẽ chia đôi vùng sắp xếp của nó ra làm 2 phần. Khi thực hiện đếm tại hàm trộn, ta chỉ cần đếm số cặp nghịch thế ở trong 2 phần (đã được tính từ trước ở khúc chia thành 2 phần), xong kết hợp với số cặp nghịch thế khi "trộn" 2 phần đó lại là có ngay giá trị cần trả ra rồi. Vây vấn đề của ta là làm sao để đếm số cặp nghịch thế khi "trộn" 2 phần lại là xong.
Nếu bạn chưa biết, ở thao tác trộn, nhiệm vụ của ta là ghép 2 dãy đã được sắp xếp tăng dần lại sao cho dãy mới duy nhất cũng là dãy được sắp xếp tăng dần. Ví dụ ta có 2 dãy $\{2,3,5,6\}$ và $\{1,3,4\}$. Sau khi "trộn" 2 dãy đó lại thành dãy mới là $\{2,3,5,6,1,3,4\}$, sau đó ta sắp xếp chúng tăng dần: $\{1,2,3,3,4,5,6\}$. Vậy dãy mới sau khi thực hiện thao tác "trộn" là $\{1,2,3,3,4,5,6\}$. Nhờ có kĩ thuật [hai con trỏ](https://wiki.vnoi.info/algo/basic/two-pointers), ta có thể giải quyết bài toán này trong $O(A+B)$ với $A,B$ lần lượt là kích thước 2 mảng cần trộn. Bạn có thể xem giải thích khá rõ ràng về cách giải bài toán này bằng hai con trỏ: https://hackmd.io/@hda/SkejOs2gn#B%C3%A0i-to%C3%A1n-2
> Mô phỏng thuật toán "trộn":
> 
> <br>
> *(Nguồn: VNOI Wiki - https://vnoi.info/wiki/algo/basic/two-pointers.md)*
**Ý tưởng chung:** Để đếm cặp nghịch thế, nhận thấy rằng khi ta bỏ $B_j$ vào dãy $C$ (nghĩa là lúc này $A_i>B_j$), các phần tử ta đã bỏ vào trong dãy $C$ trước đó đều phải bé hơn $B_j$, và nó bao gồm các phần tử từ vị trí $1$ tới $i-1$ của dãy $A$. Do vậy số $B_j$ có thể ghép cặp nghịch thế với tất cả các phần tử trong dãy $A$ mà ta đã bỏ vào dãy $C$ từ trước. Mà sắp xếp trộn là một thuật toán sắp xếp [ổn định](https://canhminhdo.github.io/blog/2020/tinh-on-dinh-cua-thuat-toan-sap-xep/) (stable) nên thứ tự các phần tử được bỏ vào $C$ trước đó so với $A$ và $B$ là không thay đổi, nghĩa là điều kiện $1 \le j<i$ cũng đã được xử lý.
Lí do ta không ghép $B_j$ với các phần tử $B_1,B_2,...,B_{j-1}$ là vì các cặp nghịch thế đó đã được tính ở hàm đệ quy tiếp theo của hàm `merge()` rồi (hiểu đơn giản là nó đã được tính ở bài toán con rồi). Vậy ta chỉ cần cài hàm `merge(...)` theo ý tưởng đó là được. Ngoài ra bạn có thể tham khảo thêm lời giải chi tiết cho bài đếm số cặp nghịch thế tại [bài viết này](https://takeuforward.org/data-structure/count-inversions-in-an-array/) nhé.
:::spoiler **Code**
```cpp=
/*
Nguồn: https://takeuforward.org/data-structure/count-inversions-in-an-array/
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;
int merge(vector<int> &arr, int low, int mid, int high) {
vector<int> temp; // temporary array
int left = low; // starting index of left half of arr
int right = mid + 1; // starting index of right half of arr
//Modification 1: cnt variable to count the pairs:
int cnt = 0;
//storing elements in the temporary array in a sorted manner//
while (left <= mid && right <= high) {
if (arr[left] <= arr[right]) {
temp.push_back(arr[left]);
left++;
}
else {
temp.push_back(arr[right]);
cnt += (mid - left + 1); //Modification 2
right++;
}
}
// if elements on the left half are still left //
while (left <= mid) {
temp.push_back(arr[left]);
left++;
}
// if elements on the right half are still left //
while (right <= high) {
temp.push_back(arr[right]);
right++;
}
// transfering all elements from temporary to arr //
for (int i = low; i <= high; i++) {
arr[i] = temp[i - low];
}
return cnt; // Modification 3
}
int mergeSort(vector<int> &arr, int low, int high) {
int cnt = 0;
if (low >= high) return cnt;
int mid = (low + high) / 2 ;
cnt += mergeSort(arr, low, mid); // left half
cnt += mergeSort(arr, mid + 1, high); // right half
cnt += merge(arr, low, mid, high); // merging sorted halves
return cnt;
}
int numberOfInversions(vector<int>&a, int n) {
// Count the number of pairs:
return mergeSort(a, 0, n - 1);
}
signed main()
{
int n;
cin>>n;
vector<int> a(n);
for(int i=0; i<n; ++i) {
cin>>a[i];
}
int cnt = numberOfInversions(a, n);
cout<< cnt << endl;
return 0;
}
```
##### Đánh giá độ phức tạp
- Độ phức tạp thời gian: $O(n\log n)$
- Độ phức tạp không gian: $O(n)$
:::
<br>
>[!Tip] **Cách 2**
> **Ý tưởng chính:** ==Fenwick Tree==
Để đếm số cặp nghịch thế thì ta sẽ dùng mảng đánh dấu: gọi $mark_k$ là số lượng phần tử trong mảng a có giá trị bằng $k$. Lúc này số phần tử bé hơn $a_i$ sẽ là $mark_1+mark_2+⋯+mark_{a_i-1}$. Sau đó ta sẽ đánh dấu $a_i$ vào $mark$ bằng cách cập nhật lại giá trị $mark_{a_i}=mark_{a_i}+1$. Dễ thấy đây chính là bài toán ứng dụng cơ bản của **[Fenwick tree](https://wiki.vnoi.info/algo/data-structures/fenwick)**. Tuy nhiên do $a_i$ có thể lên tới $10^9$ mà $n$ chỉ lên tới $2\cdot 10^5$ nên ta cần phải [nén mảng](https://blog.vietcodes.com/algo/lis#ph%C6%B0%C6%A1ng-ph%C3%A1p-n%C3%A9n-s%E1%BB%91) lại để giữ nguyên độ lớn của các phần tử.
:::spoiler **Code**
```cpp=
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5;
int a[MAXN+5],n;
int temp[MAXN+5];
void compress(){
for(int i=1;i<=n;++i){
temp[i]=a[i];
}
sort(temp+1,temp+n+1);
for(int i=1;i<=n;++i){
a[i]=lower_bound(temp+1,temp+n+1,a[i])-temp;
}
}
int BIT[MAXN+5];
void update(int idx,int value){
while(idx<=n){
BIT[idx]+=value;
idx+=idx&(-idx);
}
}
int get(int idx){
int res=0;
while(idx>0){
res+=BIT[idx];
idx-=idx&(-idx);
}
return res;
}
void solve(){
int ans=0;
for(int i=1;i<=n;++i){
ans+=get(n)-get(a[i]);
update(a[i],1);
}
cout<<ans<<'\n';
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
}
compress();
solve();
return 0;
}
```
##### Đánh giá độ phức tạp
- Độ phức tạp thời gian: $O(n\log n)$
- Độ phức tạp không gian: $O(n)$
:::
___
## Bài 2 (KHUVUC.*)
### Đề bài
Cho mảng $a$ gồm $n$ phần tử. Thay đổi một phần tử bất kỳ trong dãy thành một giá trị bất kỳ và chọn một số nguyên dương $U$ sao cho $U$ là ước của mọi phần tử của dãy và giá trị $U$ được chọn là lớn nhất.
Yêu cầu: In ra số nguyên dương $U$ lớn nhất có thể chọn được trong các cách thay đổi một phần tử bất kỳ.
**Ràng buộc:**
- Subtask $1$ (chiếm $40\%$ số điểm): $1 \le n \le 100$ và $1 \le a_i \le 100$.
- Subtask $2$ (chiếm $40\%$ số điểm): $1 \le n \le 1000$ và $1 \le a_i \le 10^9$.
- Subtask $3$ (chiếm $20\%$ số điểm): $1 \le n \le 10^5$ và $1 \le a_i \le 10^9$.
___
### Lời giải
#### Subtask 1
Để giải quyết subtask này thì ta chỉ cần chạy thử với từng vị trí một, với mỗi vị trí ta thử lần lượt thay bằng các giá trị từ $1$ tới $100$ và lấy ƯCLN của dãy sau khi thay.
##### Đánh giá độ phức tạp
- Độ phức tạp thời gian: $O(100\cdot n^2\log a)$
- Độ phức tạp không gian: $O(n)$
#### Subtask 2
Với $a_i$ là phần tử được thay đổi, để $U$ (aka. ƯCLN của dãy sau khi thay đổi) lớn nhất ta cần thay đổi $a_i$ thành ƯCLN của $n-1$ phần tử trong dãy sau khi bỏ $a_i$ đi.
:::info
**Chứng minh:**
Giả sử ta thay $a_i$ bằng $x$. Ta gọi $GCD_{i}$ là $gcd(a_1,a_2,...,a_{i-1},a_{i+1},...,a_n)$, nghĩa là ƯCLN của $n-1$ phần tử còn lại (không tính $a_i$).
Lúc này $U=gcd(x,GCD_i)$.
Ta có tính chất sau của hàm ƯCLN với $a,b>0$: $$gcd(a,b) \le b$$ Do ước của một số nguyên dương luôn không lớn hơn số đó. Đẳng thức xảy ra $\Leftrightarrow b\ |\ a$ (nghĩa là $a$ chia hết cho $b$). Áp dụng vào bài, ta có:
$$ U=gcd(x,GCD_i) \le GCD_i$$ Đẳng thức xảy ra $\Leftrightarrow$ $x$ là bội của $GCD_i$ $\Rightarrow$ ta có thể gán luôn $a_i=GCD_i$ cho cụ thể.
Vậy $U_{max}=GCD_i$, kết thúc chứng minh.
:::
Vì thế, phần tử khác đó khi thêm vào thì để ƯCLN còn lại lớn nhất thì nó là ƯCLN của $n-1$ phần tử còn lại sau khi xóa phần tử cũ đi. Vậy ta đưa về bài toán: loại bỏ 1 phần tử sao cho ƯCLN của $n-1$ phần tử còn lại của dãy là lớn nhất. Cách làm vét cạn thì cũng khá đơn giản, đó chính là tại mỗi vị trí ta thử loại bỏ phần tử đó đi và tính ƯCLN của dãy.
:::spoiler **Code**
```cpp=
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5;
vector<int>a;
int n;
int gcd(vector<int>arr,int pop_idx){
arr.erase(begin(arr)+pop_idx);
if(arr.empty())return 0;
int res=arr[0];
for(int element:arr){
res=__gcd(res,element);
}
return res;
}
void solve(){
int ans=0;
for(int i=0;i<n;++i){
ans=max(ans,gcd(a,i));
}
cout<<ans<<'\n';
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n;
a.resize(n);
for(int i=0;i<n;++i){
cin>>a[i];
}
solve();
return 0;
}
```
##### Đánh giá độ phức tạp
- Độ phức tạp thời gian: $O(n^2\log a)$
- Độ phức tạp không gian: $O(n)$
:::
#### Subtask 3
> Ý tưởng đã được nêu ở **Subtask 2**
Gọi $\text{left}_i$ là $gcd(a_1,a_2,…,a_i)$, và $\text{right}_i$ là $gcd(a_i,a_{i+1},…,a_n)$. Dễ thấy rằng sau khi loại bỏ phần tử tại vị trí $i$ thì ƯCLN của các phần tử còn lại là $gcd(\text{left}_{i-1},\text{right}_{i+1})$. Vậy ta chỉ cần 1 vòng lặp duyệt qua dãy và cập nhật giá trị lớn nhất là được.
:::spoiler **Code**
```cpp=
#include<bits/stdc++.h>
#define left sussy
#define right baka
#define int long long
using namespace std;
const int MAXN=1e5;
int a[MAXN+5],n,left[MAXN+5],right[MAXN+5];
void compute(){
left[1]=a[1];
for(int i=2;i<=n;++i){
left[i]=__gcd(left[i-1],a[i]);
}
right[n]=a[n];
for(int i=n-1;i>=1;--i){
right[i]=__gcd(right[i+1],a[i]);
}
}
void solve(){
compute();
int ans=0;
for(int i=1;i<=n;++i){
ans=max(ans,__gcd(left[i-1],right[i+1]));
}
cout<<ans<<'\n';
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
}
solve();
return 0;
}
```
##### Đánh giá độ phức tạp
- Độ phức tạp thời gian: $O(n\log a)$
- Độ phức tạp không gian: $O(n)$
:::
___
## Bài 3 (GIAIDAU.*)
### Đề bài
Cho dãy $a$ có $n$ phần tử và $q$ truy vấn. Mỗi truy vấn cho 2 số $u,v\ (u<v)$. Với mỗi truy vấn hãy tìm cách chia đoạn con gồm các phần tử $a_u,a_{u+1},…,a_v$ thành 2 phần liên tiếp sao cho chênh lệch giữa tổng 2 phần là nhỏ nhất. Nghĩa là chọn vị trí $i\ (u \le i<v)$ sao cho $|(a_u+a_{u+1}+⋯+a_i)-(a_{i+1}+a_{i+2}+⋯+a_v)|$ là nhỏ nhất.
**Ràng buộc:**
- Subtask $1$ (chiếm $40\%$ số điểm): $2 \le n \le 100$ và $1 \le q \le 100$.
- Subtask $2$ (chiếm $40\%$ số điểm): $2 \le n \le 10^3$ và $1 \le q \le 10^4$.
- Subtask $3$ (chiếm $20\%$ số điểm): $2 \le n \le 10^5$ và $1 \le q \le 10^5$.
___
### Lời giải
#### Subtask 1
Để vét cạn thì rất đơn giản, ta chạy $i$ từ $u$ tới $v-1$ và lấy min của $|(a_u+a_{u+1}+⋯+a_i)-(a_{i+1}+a_{i+2}+⋯+a_v)|$ là được.
##### Đánh giá độ phức tạp
- Độ phức tạp thời gian: $O(n^2 \times q)$
- Độ phức tạp không gian: $O(n)$
#### Subtask 2
> *"Để vét cạn thì rất đơn giản, ta chạy $i$ từ $u$ tới $v-1$ và lấy min của $|(a_u+a_{u+1}+⋯+a_i)-(a_{i+1}+a_{i+2}+⋯+a_v)|$ là được."* - **Subtask 1**
Để tính nhanh tổng một đoạn thì ta sử dụng prefix sum.
:::spoiler **Code**
```cpp=
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5;
int a[MAXN+5],n,q,prefix[MAXN+5];
void solve(){
int u,v;
cin>>u>>v;
int ans=1e18;
for(int i=u;i<v;++i){
ans=min(ans,llabs((prefix[v]-prefix[i])-(prefix[i]-prefix[u-1])));
}
cout<<ans<<'\n';
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>q;
for(int i=1;i<=n;++i){
cin>>a[i];
prefix[i]=prefix[i-1]+a[i];
}
while(q--){
solve();
}
return 0;
}
```
##### Đánh giá độ phức tạp
- Độ phức tạp thời gian: $O(n \times q)$
- Độ phức tạp không gian: $O(n)$
:::
#### Subtask 3
>[!Tip] **Cách 1**
> **Ý tưởng chính:** ==Tìm kiếm nhị phân==, ==Toán học==
Gọi $\text{prefix}_i$ là mảng cộng dồn tại $i$, hay: $\text{prefix}_i = a_1+a_2+...+a_i$.
Ta có:
- $a_u+a_{u+1}+⋯+a_i=\text{prefix}_i-\text{prefix}_{u-1}$
- $(a_{i+1}+a_{i+2}+⋯+a_v)=\text{prefix}_v-\text{prefix}_i$
Viết lại biểu thức, ta cần tìm giá trị nhỏ nhất của $|M|$ với:
$$M=(\text{prefix}_v-\text{prefix}_i )-(\text{prefix}_i-\text{prefix}_{u-1} )$$$$=\text{prefix}_{u-1}+\text{prefix}_v-2\cdot \text{prefix}_i$$
>[!Note] **Trường hợp 1**
> - $M\ge 0$
>
> Dễ thấy để $|M|$ bé nhất, mà $\text{prefix}_{u-1}+\text{prefix}_v$ là cố định nên là $2\cdot \text{prefix}_i$ phải lớn nhất!
>
> $$\text{prefix}_{u-1}+\text{prefix}_v\ge2.\text{prefix}_i$$ $$\Rightarrow \text{prefix}_i \le \frac{\text{prefix}_{u-1}+\text{prefix}_v}2$$
>
> Vậy M bé nhất khi $\text{prefix}_i$ lớn dần và càng tiến gần tới $\frac{\text{prefix}_{u-1}+\text{prefix}_v}2$.
> Để tìm được $i$ thì ta thực hiện tìm kiếm nhị phân vị trí $i$ lớn nhất thỏa mãn:
> $$\text{prefix}_i\le \frac{\text{prefix}_{u-1}+\text{prefix}_v}2$$
> Do $a_i\ge 1$ nên $\text{prefix}_{i-1}<\text{prefix}_i$, nghĩa là dãy $\text{prefix}$ đã được sắp xếp tăng dần sẵn nên ta có thể thực hiện tìm kiếm nhị phân.
>[!Note] **Trường hợp 2**
> - $M <0$
>
> Dễ thấy lúc này $|M|=2.\text{prefix}_i-(\text{prefix}_{u-1}+\text{prefix}_v)$, mà $\text{prefix}_{u-1}+\text{prefix}_v$ là cố định nên để $|M|$ bé nhất thì là $2\cdot \text{prefix}_i$ phải bé nhất!
> $$\text{prefix}_{u-1}+\text{prefix}_v<2.\text{prefix}_i$$ $$\Rightarrow \text{prefix}_i>\frac{\text{prefix}_{u-1}+\text{prefix}_v}2$$
>
> Vậy $|M|$ bé nhất khi $\text{prefix}_i$ nhỏ dần và càng tiến gần tới $\frac{\text{prefix}_{u-1}+\text{prefix}_v}2$.
> Để tìm được $i$ thì ta thực hiện tìm kiếm nhị phân vị trí $i$ nhỏ nhất thỏa mãn:
> $$\text{prefix}_i>\frac{\text{prefix}_{u-1}+\text{prefix}_v}2$$
Để tránh sử dụng 2 lần tìm kiếm nhị phân thì nhận thấy rằng giá trị ở 2 trường hợp đều có chung vế phải là $\frac{\text{prefix}_{u-1}+\text{prefix}_v}2$, chỉ khác mỗi dấu là $\le$ và $>$. Nhận thấy rằng 2 dấu này ngược nhau nên nếu tìm được $i$ bé nhất thỏa:
$$\text{prefix}_i>\frac{\text{prefix}_{u-1}+\text{prefix}_v}2$$ thì ta phải tìm giá trị của $i'$ lớn nhất thỏa:
$$\text{prefix}_{i'}\le \frac{\text{prefix}_{u-1}+\text{prefix}_v}2$$
$\Rightarrow i'=i-1$ (do $i$ là giá trị nhỏ nhất thỏa $>$ thì $i-1$ sẽ là giá trị lớn nhất thỏa dấu $\le$)
Sau đó ta lấy giá trị nhỏ nhất của 2 trường hợp là được.
:::spoiler **Code**
```cpp=
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5;
int a[MAXN+5],n,q,prefix[MAXN+5];
void solve(){
int u,v;
cin>>u>>v;
int mid=(prefix[u-1]+prefix[v])/2;
int idx=upper_bound(prefix+u,prefix+v+1,mid)-prefix;
int ans1=llabs(prefix[u-1]+prefix[v]-2*prefix[idx]),
ans2=llabs(prefix[u-1]+prefix[v]-2*prefix[idx-1]);
cout<<min(ans1,ans2)<<'\n';
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>q;
for(int i=1;i<=n;++i){
cin>>a[i];
prefix[i]=prefix[i-1]+a[i];
}
while(q--){
solve();
}
return 0;
}
```
##### Đánh giá độ phức tạp
- Độ phức tạp thời gian: $O(n + q\log n)$
- Độ phức tạp không gian: $O(n)$
:::
<br>
>[!Tip] **Cách 2**
> **Ý tưởng chính:** ==Tìm kiếm nhị phân (theo kết quả)==/==Chặt nhị phân==
>
> :::success
>
> Lời giải được đóng góp bởi một thành viên ẩn danh trong group **[LHPIC 2024-2025](https://zalo.me/g/lxnzlj539)**
>
> :::
Giả sử ta sẽ chia đôi đoạn con tại vị trí $\text{mid}$.
Ta gọi $\text{left}$ là tổng phần bên trái, và $\text{right}$ là tổng phần bên phải. Cụ thể:
- $\text{left} = a_1+a_2+...+a_{\text{mid}} = \text{prefix}_{\text{mid}} - \text{prefix}_{u-1}$
- $\text{right} = a_{\text{mid}+1}+a_{\text{mid}+2}+...+a_v = \text{prefix}_v - \text{prefix}_{\text{mid}}$
Lúc này chênh lệch giữa 2 phần là $|\text{right}-\text{left}|$
Nếu $\text{left}<\text{right}$, nghĩa là ta có thể "hi vọng" vào một chênh lệch nhỏ hơn bằng cách tăng $\text{left}$ lên, điều này tương đương với việc $\text{right}$ sẽ giảm xuống do $\text{left}+\text{right}=a_u+a_{u+1}+...+a_v$ là cố định. Việc $\text{left}$ tăng và $\text{right}$ giảm sẽ khiến chúng đến "gần" nhau hơn, từ đó giúp ta có khả năng được một chênh lệch nhỏ hơn.
Ngược lại, nếu $\text{left} > \text{right}$ thì ta cũng có thể "hi vọng" vào một chênh lệch nhỏ hơn bằng cách giảm $\text{left}$ đi và tăng $\text{right}$ lên.
Còn với trường hợp $\text{left}=\text{right}$, dẫn đến chênh lệch của chúng là $|\text{right}-\text{left}|=0$, thì ta không cần phải chạy nữa do $0$ là chênh lệch nhỏ nhất mà ta có thể đạt được.
Ta cần nghĩ cách để tăng hoặc giảm $\text{left}$ một cách hiệu quả. Nhận ra rằng $a_i \ge 1$ nên nếu ta muốn tăng tổng của một phần lên thì đơn giản chỉ cần lấy thêm một phần tử bất kì nữa vào là được. Do vậy để tăng $\text{left}$ lên thì ta chỉ cần tăng $\text{mid}$ lên, và để giảm $\text{left}$ thì ta cũng chỉ cần giảm $\text{mid}$ xuống.
Từ đây dễ dàng nhận ra ta có thể tìm kiếm nhị phân (chặt nhị phân) theo vị trí chia đôi. Để kiểm soát miền giá trị của $\text{mid}$ ta sử dụng 2 biến $\text{low}$ và $\text{high}$. Đồng thời ta cập nhật chênh lệch nhỏ nhất tại mỗi vị trí $\text{mid}$ ta chọn.
:::spoiler **Code**
```cpp=
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5;
int a[MAXN+5],n,q,prefix[MAXN+5];
void solve(){
int u,v;
cin>>u>>v;
int low=u,high=v;
int ans=1e18;
while(low<=high){
int mid=(low+high)/2;
int left=prefix[mid]-prefix[u-1],
right=prefix[v]-prefix[mid];
ans=min(ans,llabs(right-left));
if(left<right){
low=mid+1;
}
else if(left>right){
high=mid-1;
}
else break;
}
cout<<ans<<'\n';
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>q;
for(int i=1;i<=n;++i){
cin>>a[i];
prefix[i]=prefix[i-1]+a[i];
}
while(q--){
solve();
}
return 0;
}
```
##### Đánh giá độ phức tạp
- Độ phức tạp thời gian: $O(n + q\log n)$
- Độ phức tạp không gian: $O(n)$
:::
---
## Tổng kết
### Nhận xét đề
- Theo mình thì đề HSG9 TP.HCM năm nay không hề khó, đặc biệt ở 2 bài cuối khi ta chỉ cần suy luận một xíu là đã ra rồi. Tuy nhiên nhiều bạn mất giải Nhất do Bài 1 mang tính đánh đố thí sinh, khi hầu hết không ai biết cách đếm số cặp nghịch thế bằng **Sắp xếp trộn**, còn dùng **Fenwick tree** thì nhiều bạn lại chưa học. Với một người đã học Fenwick tree từ trước như mình thì đề này hoàn toàn không hề khó :Đ
### Lời kết
Vậy là mình vừa giải xong đề HSG9 TP.HCM môn Tin học năm học 2024-2025. Hi vọng bạn thấy lời giải này hữu ích và dễ hiểu :Đ.
> Dĩ nhiên trong lời giải cũng không thể tránh khỏi sai sót, nên là nếu các bạn đọc phát hiện ra bất kì lỗi nào thì hãy liên hệ với mình (@hungg261). Mình sẽ cố gắng sửa lại trong thời gian sớm nhất!
**Bye bye!** :penguin:
<br>
## Tài liệu
- https://wiki.vnoi.info/algo/data-structures/fenwick
+ https://oj.vnoi.info/problem/nkinv (bài đếm số cặp nghịch thế)
- https://cp-algorithms.com/data_structures/fenwick.html
- https://takeuforward.org/data-structure/count-inversions-in-an-array/
- https://drive.google.com/file/d/1oog65SuQzWpTUjOnRL5NTSfOFd5JoSyY/view
- https://fb.watch/yXEd5ELhYp/ (livestream giải đề của TGB)
- https://www.facebook.com/share/p/1648r5ZTU8/ (bài post lời giải của mình ngay sau khi thi)
- https://github.com/hungg261/baitap-quanTB_24-25/tree/main/solutions/hsg9_tphcm2025-sol (lời giải trên Github của mình)
Sign in with Wallet
Connect another wallet