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);
}
```
HaoVoxx
Created at
5 likes