Chào các bạn, đây là solution của bài Dãy con tăng 2, tuy nhiên hãy đọc nếu bạn quá bí nhé!
Tại đây, khi nhìn vào đề bài, ta sẽ ngã ngửa khi thấy giới hạn của n là <= 100000.
Là giới hạn khá là lớn. Tuy vậy, ta vẫn có thể giải nó trong O(nlogn) thay vì thuật toán 2 for bình thường là O(n * n).
Thì thường thấy, chúng ta sẽ cần nghĩ đến những gì khi có thuật toán O(nlogn) ? Đúng vậy, đó là tìm kiếm nhị phân.
Bạn có thể tham khảo tại đây: https://vietcodes.github.io/code/82/index.html
Tuy nhiên, đoạn code trên hơi khó hiểu và trong vài trường hợp như cần truy vết nó sẽ không làm tốt được.
Mình sẽ chỉ bạn Phương pháp 2, đó là Binary Index Tree (BIT) hay còn gọi là Fenwick Tree.
Đầu tiên khởi tạo 1 cái cây Fenwick Tree bình thường, nhưng sẽ lưu trữ các giá trị max.
Tại sao ư ? Tại vì BIT có đặc điểm khác các thuật quản lý đoạn khác như IT,... là nó không thể cập nhật các giá trị nào mà nhỏ hơn giá trị gần nhất nó cập nhật
Có nghĩa là khi đưa vào giá trị [3] thì các giá trị như [2], [1] sẽ không được cập nhật
Lợi dụng điểm đó, ta sẽ nghĩ đến việc cập nhật các giá trị ai một các hợp lý
update(ai, dpi): Cập nhật giá trị của dpi vào cây Fenwick tại vị trí ai.
get(ai - 1): Lấy giá trị lớn nhất từ vị trí 1 đến ai - 1 trong cây Fenwick. Điều này cung cấp thông tin về các phần tử trước ai trong mảng a.
Bài toán này đang cố gắng tìm dãy con tăng dài nhất, và giá trị của dpi được cập nhật để đảm bảo rằng nó chứa đựng chiều dài lớn nhất của dãy con tăng kết thúc tại vị trí i.
dpi = get(ai - 1) + 1: Giá trị dpi sẽ được cập nhật là độ dài lớn nhất của dãy con kết thúc tại i, mà có phần tử cuối cùng nhỏ hơn ai. Bằng cách lấy giá trị lớn nhất từ cây Fenwick cho các phần tử nhỏ hơn ai và cộng thêm 1 (đại diện cho ai chính nó), ta có thể cập nhật độ dài của dãy con tăng tại vị trí i.
Khi đã cập nhật dpi, ta cũng cần cập nhật cây Fenwick tại vị trí ai để có thể sử dụng thông tin này cho các vị trí tiếp theo trong quá trình duyệt.
ok vậy code như vậy đã ổn chưa?
chưa đâu, bạn chỉ mới giải quyết 1/2 bài toán, bởi còn 1 thứ nữa cần giải quyết là giới hạn của ai
Như bạn thấy, việc chúng ta cập nhật thẳng ai và BIT sẽ phải duyệt đến giới hạn ai. Tức là ta phải duyệt đến 10^9 phần tử.
Và một cái mảng (tiêu chuẩn C++) chỉ có thể duyệt đến 10^6 là cao nhất (có thể 10^7 tùy máy chấm).
Vậy ta phải làm sao? Để giải quyết ta cần phải nén giá trị của ai để giảm xuống giới hạn cần duyệt
Bạn có thể nén nhiều cách, mình không bắt buộc ai, ở đây mình sẽ sử dụng nén tọa độ (vị trí) để làm bài
Tham khảo Code:
```cpp
#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target ("avx2")
//fb.com/HaoVoxx
#define readln(x) getline(cin, (x))
#define file "f"
#define endl '\n'
#define pb push_back
#define st first
#define nd second
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const ll MOD = 1e9 + 7;
const ll INF = LLONG_MAX;
const ll dx[] = {0, 0, -1, 1, 1, -1, 1, -1};
const ll dy[] = {-1, 1, 0, 0, -1, 1, 1, -1};
const int N = 1e5 + 5;
ll tree[N];
vector <ll> a(N);
int n;
void upd(ll x, ll val){
for(; x < N; x += x & (-x)){
tree[x] = max(tree[x], val);
}
}
ll emrua(ll x){
ll maxx = 0;
for(; x > 0; x -= x & (-x)){
maxx = max(maxx, tree[x]);
}
return maxx;
}
void toiuu();
void solve();
int main(){
//freopen(file".INP", "r", stdin);
//freopen(file".OUT", "w", stdout);
toiuu();
solve();
return 0;
}
void toiuu(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
void solve(){
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
vector <int> zip;
for(ll x : a){
ll l = x;
zip.pb(l);
}
sort(all(zip));
zip.erase(unique(all(zip)), zip.end());
for(ll &x : a){
ll &l = x;
l = lower_bound(all(zip), l) - zip.begin() + 4;
}
ll dp[n + 1];
for(int i = 1; i <= n; i++){
dp[i] = emrua(a[i] - 1) + 1;// trừ 1 vì ai < aj, nếu ai <= aj thì không trừ 1
upd(a[i], dp[i]);
}
cout << *max_element(dp + 1, dp + 1 + n);
}
```
# TÌm độ dài dãy con tăng dài nhất bằng tìm kiếm nhị phân
Cách làm $O(n^2)$ cho bài toán dãy con tăng thông thường
$$dp[i] = dp[j] + 1$$
Nếu $j < i$ và $a[i] < a[j]$
Để cải tiến thuật toán này chúng ta sẽ sử dụng cách làm tìm kiếm nhị phân và tham lam như sau
Gọi mảng $b$, với $b[j]$ mang ý nghĩa: $b[j]$ là giá trị nhỏ nhất của phần tử cuối cùng, trong số tất cả các dãy con tăng độ dài là $j$
##### Ví dụ
Dãy $a$ có các dãy con tăng độ dài $3$ là
- [$1, 3, 7$]
- [$2, 3, 9$]
- [$1, 3, 5$]
Thì $b[3] = 5$, do trong $3$ dãy này, dãy [$1, 3, 5$] có phần tử cuối nhỏ nhất.
Vậy khi muốn tìm ra dãy con tăng dài nhất kết thúc tại $i$, ta có thể tìm được bằng một dòng code $O(n^2)$ đơn giản sau
##### Code trâu
```cpp
for (int j=1; j<=n; j++) b[j] = oo;
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
if (b[j] < a[i]) dp[i] = max(dp[i], j+1);
}
// có dãy con tăng độ dài x kết thúc tại i, thì cũng có dãy con tăng độ dài x-1 kết thúc tại i
for (int j=1; j<=dp[i]; j++) {
b[j] = min(b[j], a[i]);
}
}
```
Ta thấy mảng $b$ có tính chất $b[i] < b[i+1]$ với mọi $i$.
Vậy thay vì dùng vòng for để tìm ra $j$ tốt nhất, ta có thể tìm kiếm nhị phân phần tử $b[j]$ cuối cùng mà còn nhỏ hơn $a[i]$, khi đó ta tạo ra được dãy con tăng độ dài $j+1$, $dp[i] = j+1$.
Nhưng vì lúc này $b[j] < a[i]$ nên $b[1], b[2], ..., b[j-1]$ cũng nhỏ hơn $a[i]$. Và ta cũng biết được $a[i] <= b[j+1]$ do tính chất của tìm kiếm nhị phân.
Vậy việc ta cần lúc này đó là ghi đè giá trị của $a[i]$ lên vị trí $b[dp[i]]$ hay chính là $b[j+1]$.
## Để hiểu chi tiết hơn, bạn có thể xem tại video này
[Dãy Con Tăng Dài Nhất sử dụng Tìm Kiếm Nhị Phân - YugiHacker](https://www.youtube.com/watch?v=yuVY9Hk7TYE)
## Code
```cpp
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int n, a[maxn], b[maxn];
int main () {
cin >> n;
for (int i=1; i<=n; i++) {
cin >> a[i];
b[i] = a[i];
}
int ans = 0;
for (int i=1; i<=n; i++) {
int j = lower_bound(b+1, b+ans+1, a[i]) - b;
b[j] = a[i];
if (j > ans) ans = j;
}
cout << ans;
}
```
HaoVoxx
Created at
11 likes
YugiHacker
Created at
4 likes