Hướng dẫn giải của Cáp treo 3

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Xét thuật toán tính LIS, ~d_x~ là giá trị cuối cùng nhỏ nhất của dãy con có độ dài ~x~. Khi thêm vào một số ~a_i~ ta cần tìm giá trị ~d_j < a_i~ sao cho ~j~ là lớn nhất rồi gán ~d_{j}=a_i~. Ở bài toán này cần xem xét đến toàn bộ các dãy con tăng nên thay vì lưu ~d_x~ là một giá trị thì lưu là một mảng, thay vì gán ~a_i~ thì cho vào cuối của mảng. Khi tìm ~j~ thì xét phần tử cuối của mảng.

Nhận xét rằng trong mảng ~d_x~ bất kì thì giá trị không bao giờ tăng vì nếu tăng giá trị đó sẽ ở ~d_y~ với ~y>x~. Tạo một những mảng ~f_x~ tương ứng với từng phần tử của các ~d_x~ là số lượng các dãy con tăng kết thúc ở giá trị đó, ~p_x~ là mảng tổng tiền tố của ~f_x~ (dùng tổng tiền tố để tính nhanh hơn). Kết quả là phần tử cuối cùng của ~p_k~ với ~k~ là độ dài LIS.

Code:

#include <bits/stdc++.h>
using namespace std;

#define pi pair<int, int>
#define inf 0x3f3f3f3f
#define all(x) x.begin(), x.end()
#define int long long
#define setinf(d) memset(d, inf, sizeof d)
#define setneg(d) memset(d, -1, sizeof d)
#define set0(d) memset(d, 0, sizeof d)
#define Log2(x) 63 - __builtin_clzll(x)
#define oo 2e18
#define mod 1000000007

const int maxn = 1e5 + 5;

int n, ans = 0;
int a[maxn];

vector<int> d[maxn];
vector<int> pre[maxn];
vector<int> v;

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i], v.push_back(a[i]);
    sort(all(v));
    v.erase(unique(all(v)), v.end());

    for(int i = 1; i < maxn; i++){
        d[i].push_back(oo);    
        pre[i].push_back(0);
    }

    d[0].push_back(oo);
    d[0].push_back(-oo);
    pre[0].push_back(0);
    pre[0].push_back(1);

    for(int i = 1; i <= n; i++){
        int l = 1, r = n, lis = 1;
        while(l <= r){
            int m = (l + r) >> 1;
            if(d[m - 1].back() < a[i]) lis = m, l = m + 1;
            else r = m - 1;
        }
        ans = max(ans, lis);
        l = 0, r = d[lis - 1].size(); int p = 0;

        while(l <= r){
            int m = (l + r) >> 1;
            if(d[lis - 1][m] < a[i]) p = m, r = m - 1;
            else l = m + 1;
        }

        d[lis].push_back(a[i]);
        pre[lis].push_back((pre[lis].back() + pre[lis - 1].back() - pre[lis - 1][p - 1] + mod) % mod);
    }
    cout << pre[ans].back();
}