---
title:
Standard template library (Phần 4: Chữa bài tập)
---
Standard template library (Phần 4: Chữa bài tập)
===
---
###### ✍️ Author: 2School Guideline
###### 📋 Content:
[TOC]
---
## [Bài 1 - Nearest Smaller Values](https://cses.fi/problemset/task/1645)
Cho một mảng $a$ gồm $n$ phần tử. Với mỗi vị trí $i$, tìm phần tử gần nhất về bên trái bé hơn $a_i$.
### Input
- Dòng đầu tiên chứa số $n$: Số lượng phần tử trong mảng. $(1 \le n \le 2 \cdot 10^5)$
- Dòng thứ 2 chứa $n$ số $a_i$ cách nhau bởi dấu khoảng trắng. $(1 \le a_i \le 10^9)$
### Output
- Với mỗi vị trí $i$, in ra kết quả bài toán. Nếu không có in ra $0$.
### Sample input
```
8
2 5 1 4 8 3 2 5
```
### Sample output
```
0 1 0 3 4 3 3 7
```
### Lời giải
:::spoiler **Hướng dẫn giải**
Để giải quyết bài này, ta sẽ duy trì một stack $st$ để lưu vị trí ($index$) của mảng $a$ và duyệt mảng từ trái qua phải. Với mỗi vị trí $i$, ta sẽ tính $ans_i$, là phần tử gần nhất bé hơn về bên trái của $a_i$, ta sẽ chia ra được các trường hợp như sau ($index$ là chỉ số nằm ở đỉnh stack $st$ và $i$ là chỉ số hiện tại đang duyệt $a$.):
- Nếu $a[index] \ge a[i]$, thì ta sẽ loại bỏ phần tử này ra khỏi $st$. Lí do là vì $a[index] \ge a[i]$ thì với mọi $j > i$ và $a[j] \ge a[index]$ sẽ luôn thoả mãn $a[j] \ge a[i]$ nên ta sẽ luôn lấy $i$ cho những trường hợp đó và $index$ sẽ bị thừa ra.
- Nếu $a[index] < a[i]$, thì $ans_i = index$, bởi vì $st$ lưu trữ phần tử gần với $i$ nhất bé hơn $a_i$. Sau đó ta thêm $i$ vào $st$.
:::
::: spoiler **Code mẫu**
```cpp=
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5 + 5;
int a[maxn];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
stack<int> q;
for (int i = 1; i <= n; i++) {
while (!q.empty() && a[q.top()] >= a[i]) q.pop();
if (q.empty()) {
cout << 0 << " ";
} else {
cout << q.top() << " ";
}
q.push(i);
}
return 0;
}
```
:::
## [Bài 2 - Maximum Subarray Sum II](https://cses.fi/problemset/task/1644)
Cho dãy số nguyên a gồm $N$ phần tử và hai số nguyên dương $L, R \le N$. Bạn được yêu cầu tìm dãy con liên tiếp có tổng lớn nhất sao cho độ dài của nó nằm trong đoạn $[L, R]$.
### Input
- Dòng đầu chứa ba số nguyên $N, L, R$ $(L \le R \le N \le 10^5)$.
- Dòng thứ hai chứa $N$ số nguyên miêu tả dãy $a$. $(|a_i| \le 10^9)$.
### Output
Một số nguyên – Tổng lớn nhất tìm được.
### Sample input
```
9 2 3
40 -39 0 3 -5 0 3 0 1
```
### Sample output
```
4
```
### Lời giải
::: spoiler **Hướng dẫn giải**
Gọi $pref[i] = a[1] + a[2] + ... + a[i]$, ở bước này ta sẽ sử dụng kĩ thuật mảng cộng dồn đã được học ở những bài viết trước.
Để tính tổng trong đoạn $[A, B]$, ta sẽ dùng công thức $pref[B] - pref[A - 1]$.
Để đơn giản hơn, ta tạm thời không xét điều kiện độ dài nằm trong đoạn $[L, R]$. Vậy ta cố định vị trí $B$, để $pref[B] - pref[A - 1]$ là lớn nhất, tương đương với $pref[A - 1]$ phải là nhỏ nhất. Hay với mỗi $B$, $ans = max(ans, pref[B] - min\_pref[B - 1])$ với $min\_pref[i]$ là prefix sum nhỏ nhất trong đoạn từ $1$ đến $i$.
Quay trở lại bài toán trên, ta sẽ biến đổi một chút như sau: $L \le B - (A - 1) \le R \Leftrightarrow B - R \le A - 1 \le B - L$. Vậy với mỗi $B$, ta sẽ tìm $pref[A - 1]$ nhỏ nhất với $A - 1$ nằm trong đoạn từ $[B - R, B - L]$.
Lúc này ta sẽ áp dụng một kĩ thuật đã được nhắc trong mục deque [(Tìm max min trên đoạn tịnh tiến)](https://hackmd.io/@2SchoolGuideline/S1XcVF7rT#Đề-bài-Chủ-đề-Tìm-max-min-trên-đoạn-tịnh-tiến). Vì phần này khá giống với lời giải tìm max min trên đoạn tịnh tiến đã làm trước đó nên chúng mình sẽ không đề cập lại về kĩ thuật này tại đây.
:::
::: spoiler **Code mẫu**
```cpp=
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5 + 5;
const ll INFLL = (ll)1e18 + 7;
ll a[maxn], pref[maxn];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, l, r; cin >> n >> l >> r;
for (int i = 1; i <= n; i++) cin >> a[i], pref[i] = pref[i - 1] + a[i];
ll ans = -INFLL;
deque<int> dq;
for (int i = l; i <= n; i++) {
while (!dq.empty() && pref[dq.back()] >= pref[i - l]) dq.pop_back();
dq.push_back(i - l);
if (dq.front() < i - r) dq.pop_front();
if (!dq.empty()) ans = max(ans, pref[i] - pref[dq.front()]);
}
cout << ans;
return 0;
}
```
:::
## [Bài 3 - QBRECT](https://oj.vnoi.info/problem/qbrect)
Cho một bảng kích thước $M \times N$, được chia thành lưới ô vuông đơn vị $M$ dòng $N$ cột $(1 \le M, N \le 1000)$
Trên các ô của bảng ghi số $0$ hoặc $1$. Các dòng của bảng được đánh số $1, 2, ..., M$ theo thứ tự từ trên xuống dưới và các cột của bảng được đánh số $1, 2, ..., N$ theo thứ tự từ trái qua phải.
**Yêu cầu:** Hãy tìm một hình chữ nhật gồm các ô của bảng thoả mãn các điều kiện sau:
- Hình chữ nhật đó chỉ gồm các số $1$.
- Cạnh hình chữ nhật song song với cạnh bảng.
- Diện tích hình chữ nhật là lớn nhất có thể.
### Input
- Dòng $1$: Ghi hai số $M,N$
- Dòng thứ $i$ trong $M$ dòng tiếp theo: Ghi $N$ số mà số thứ $j$ là số ghi trên ô $(i, j)$ của bảng
### Output
Gồm $1$ dòng duy nhất ghi diện tích của hình chữ nhật tìm được
### Sample Input
```
11 13
0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 1 1 1 1 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 1 1
0 0 0 0 0 1 0 0 0 0 0 1 1
```
### Sample Output
```
49
```
### Lời giải
:::spoiler **Hướng dẫn giải**
Với mỗi hàng $i \space (1 \le i \le m)$, gọi $f(j)$ là độ cao của ô $1$ ở cột thứ $j$. Ví dụ, ở hàng thứ $9$, độ cao tại cột $3$ là $f(3) = 7$, độ cao ở cột $5$ là $f(5) = 8$
Vậy với mỗi $j \space (1 \le i \le n)$, ta tìm một đoạn $[L, R]$ mà đoạn này nhận $f(j)$ là giá trị nhỏ nhất. Khi đó kết quả tại hàng này sẽ là $ans = max(ans, f(j) \times (R - L + 1))$
Gọi $l(j)$ là vị trí gần với $j$ về bên trái nhất sao cho $f(l(j)) < f(j)$. Vậy đoạn $[l(j) + 1, j]$ sẽ nhận $f(j)$ là giá trị nhỏ nhất.
Gọi $r(j)$ là vị trí gần với $j$ về bên phải nhất sao cho $f(r(j)) < f(j)$. Vậy đoạn $[j, r(j) - 1]$ sẽ nhận $f(j)$ là giá trị nhỏ nhất.
Hợp cả 2 đoạn lại thì ta được đoạn $[l(j) + 1, r(j) - 1]$ sẽ nhận $f(j)$ là giá trị nhỏ nhất.
Để tìm được mảng $l(j), r(j)$ ta áp dụng kĩ thuật đã được sử dụng ở [Bài 1](#Bài-1).
:::
:::spoiler **Code mẫu**
```cpp=
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[1005][1005], f[1005], l[1005], r[1005];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int m, n; cin >> m >> n;
for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) cin >> a[i][j];
int ans = 0;
for (int i = 1; i <= m; i++) {
// f[j] la do cao cua o 1 lien tiep voi 1 <= j <= n
for (int j = 1; j <= n; j++) {
if (a[i][j] == 0) f[j] = 0;
else f[j]++;
}
// l[j] la vi tri f ben trai gan nhat < f[j]
// r[j] la vi tri f ben phai gan nhat < f[j]
deque<int> q;
for (int j = 1; j <= n; j++) {
while (!q.empty() && f[q.back()] >= f[j]) q.pop_back();
if (q.empty()) l[j] = 0;
else l[j] = q.back();
q.push_back(j);
}
q.clear();
for (int j = n; j >= 1; j--) {
while (!q.empty() && f[q.back()] >= f[j]) q.pop_back();
if (q.empty()) r[j] = n + 1;
else r[j] = q.back();
q.push_back(j);
}
for (int j = 1; j <= n; j++) ans = max(ans, f[j]*(r[j] - l[j] - 1));
}
cout << ans;
return 0;
}
```
:::
## [Bài 4 - Remove Extra One](https://codeforces.com/contest/900/problem/C)
Cho một hoán vị $p$ gồm $n$ phần tử. Tìm cách xoá duy nhất một phần tử sao cho số lượng ***record*** là lớn nhất.
Ta định nghĩa $A_i$ là một ***record*** khi với mọi $j \space (1 \le j < i)$ thì $A_j < A_i$.
Một hoán vị $p$ là một dãy các số nguyên từ $1$ đến $n$ có độ dài $n$ chứa mỗi số đúng 1 lần được sắp xếp không theo thứ tự. **Ví dụ:** $(1), (4, 3, 5, 1, 2), (3, 2, 1)$ là một hoán vị, $(1, 1), (4, 3, 1), (2, 3, 4)$ không phải là một hoán vị.
### Input
- Dòng đầu chứa một số $n \space (1 \le n \le 10^5)$.
- Dòng thứ hai chứa $n$ số $a_1, a_2, ..., a_n \space (1 \le a_i \le n)$ - một hoán vị. Tất cả các số đảm bảo khác nhau.
### Output
- Chứa một số là phần tử cần bị xoá để số lượng ***record*** là nhiều nhất. Nếu có nhiều kết quả, in kết quả có giá trị nhỏ nhất.
### Sample input 1
```
1
1
```
### Sample output 1
```
1
```
### Giải thích 1
- Chỉ có một phần tử để xoá là phần tử $1$
### Sample input 2
```
5
5 1 2 3 4
```
### Sample output 2
```
5
```
### Giải thích
- Xoá phần tử $5$, số lượng ***record*** là $(2, 3, 4)$
### Lời giải
:::spoiler **Hướng dẫn giải**
- Với bài này thì ta cần xóa 1 phần tử sao cho số ***record*** là lớn nhất
- Gọi mảng `record` là mảng chỉ chứa giá trị $0$ và $1$ để cho ta biết là phần tử có giá trị $a_i$ có phải là 1 ***record*** lúc đầu hay không. Ta có thể tiền xử lí mảng này trong $O(n)$
- Gọi mảng $can\_be\_removed$ là mảng để lưu số phần tử $j > i$ sẽ trở thành ***record*** nếu lúc đầu nó không phải là 1 ***record*** sau khi phần tử $i$ bị xóa đi.
- Ta thực hiện bằng cách dùng ctdl `set` (vì đây là 1 dãy hoán vị nên không có phần tử lặp nên không cần thiết dùng tới `multiset`) để lưu lại giá trị của tất cả phần tử đứng trước $i$, nếu $a_i$ là phần tử lớn nhất sau khi được đưa vào `set` thì ngay từ đầu $a_i$ chính là 1 ***record*** hoặc nếu $a_i$ là phần tử lớn thứ 2 thì $can\_be\_removed$ của giá trị phần tử lớn nhất sẽ được tăng lên 1
- Cuối cùng, duyệt qua tất cả giá trị từ $1 \rightarrow n$ và tìm giá trị lớn nhất của giá trị $ans = cnt - record_i + can\_be\_removed$ ($cnt$ là số lượng phần tử ***record*** ban đầu) và đáp án sẽ là $i$ với $ans$ lớn nhất
:::
:::spoiler **Code mẫu**
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
vector <int> a(n+1);
for (int i = 1; i <= n; ++i) cin >> a[i];
// trường hợp đặc biệt
if (n == 1)
{
cout << 1 << '\n';
return 0;
}
//
int cnt = 0;
vector <bool> record(n+1);
vector <int> can_be_removed(n+1);
set <int> s;
//
record[a[1]] = 1;
s.insert(a[1]);
++cnt;
//
for (int i = 2; i <= n; ++i)
{
s.insert(a[i]);
auto last = s.end(); --last;
auto pre_last = last; --pre_last;
if (*last == a[i])
{
++cnt;
record[a[i]] = 1;
}
else if (*pre_last == a[i])
can_be_removed[*last]++;
}
//
int val = 0, ans;
for (int i = 1; i <= n; ++i)
{
int temp_val = cnt - record[i] + can_be_removed[i];
if (temp_val > val)
{
val = temp_val;
ans = i;
}
}
cout << ans << '\n';
//
return 0;
}
```
:::
## [Bài 5 - MTDANCE](https://www.spoj.com/THPTCBT/problems/MTDANCE/)
Lớp học múa khiêu vũ dạ hội của giáo sư Padegras có $n$ học sinh nam và nữ ghi tên. Giáo sư cho tất cả học sinh xếp thành một hàng dọc và chọn một số nhóm học sinh liên tiếp nhau cho buổi học đầu tiên với yêu cầu là số học sinh nam và nữ phải bằng nhau.
Hãy xác định, giáo sư Padegras có bao nhiêu cách lựa chọn khác nhau cho buổi học đầu tiên.
### Input
- Dòng đầu chứa số nguyên dương $n (1 \le n \le 10^6)$.
- Dòng thứ hai chưa xâu độ dài $n$ gồm các kí tự từ tập $\{a, b\}$ xác định dòng xếp hàng, $a$ là nam, $b$ là nữ.
### Output
- Một dòng duy nhất là số cách lựa chọn.
### Sample input
```
8
abbababa
```
### Sample output
```
13
```
### Lời giải
::: spoiler **Hướng dẫn giải**
Gọi $pref1[i]$ là số học sinh nam trong đoạn từ $1$ đến $i$.
Gọi $pref2[i]$ là số học sinh nữ trong đoạn từ $1$ đến $i$.
Ta sẽ cố định vị trí $i$, lúc này đề yêu cầu đếm số lượng $j \space (1 \le j \le i)$ thoả mãn điều kiện $pref1[i] - pref1[j - 1] = pref2[i] - pref2[j - 1] \Leftrightarrow pref1[i] - pref2[i] = pref1[j - 1] - pref2[j - 1]$
Vậy lúc này ta chỉ cần sử dụng một mảng đếm $mp[pref1[i] - pref2[i]]$ để biết được xem có bao nhiêu cặp $j$ trước đó thoả mãn $pref1[i] - pref2[i] = pref1[j - 1] - pref2[j - 1]$, đồng thời chúng ta cũng sẽ `mp[pref1[i] - pref2[i]]++` để tăng kết quả tại thời điểm $i$ lên.
**Lưu ý:** Khởi tạo `mp[0] = 1` vì có khả năng đoạn từ $1$ đến $i$ thoả mãn điều kiện $pref1[i] = pref2[i]$ hay $pref1[i] - pref2[i] = 0$
:::
::: spoiler **Code mẫu**
```cpp=
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e6 + 5;
ll pref1[maxn], pref2[maxn];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
string s; cin >> s;
for (int i = 1; i <= n; i++) {
pref1[i] = pref1[i - 1];
pref2[i] = pref2[i - 1];
if (s[i - 1] == 'a') pref1[i]++;
else pref2[i]++;
}
map<ll, int> mp;
ll ans = 0;
mp[0] = 1;
for (int i = 1; i <= n; i++) {
ans += mp[pref1[i] - pref2[i]];
mp[pref1[i] - pref2[i]]++;
}
cout << ans;
return 0;
}
```
:::
Sign in with Wallet
Connect another wallet