Trong bài viết trước, chúng ta đã cùng nhau xem xét những kiến thức tổng quan về cấu trúc dữ liệu Cây phân đoạn, hay còn gọi là Segment Tree, Interval Tree. Các bạn có thể xem lại bài viết về chủ đề trên tại đây.

Ở bài viết này, tôi sẽ giới thiệu tới các bạn một số bài toán cơ bản sử dụng Cây phân đoạn, với mục tiêu làm rõ chức năng giảm độ phức tạp thuật toán của cấu trúc dữ liệu này, đồng thời giúp các bạn có cái nhìn tổng quan hơn về cách áp dụng nó trong các bài toán lập trình cụ thể.

Bài toán 1: Dãy con tăng dài nhất

Đề bài

Cho dãy số $A$ gồm $n$ phần tử $a_1, a_2, \dots, a_n$. Một dãy con của dãy số là cách chọn ra hoặc một số phần tử (có thể không liên tiếp) của dãy.

Yêu cầu: Tìm dãy con tăng ngặt dài nhất của dãy $A?$

Input:

• Dòng đầu chứa số nguyên dương $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ phân tách nhau bởi dấu cách.

Ràng buộc:

• $1 \le n \le 10^6$.
• $|a_i| \le 10^9; \forall i: 1 \le i \le n$.

Output:

• In ra độ dài dãy con tăng ngặt dài nhất tìm được.

Sample Input:

5
2 1 4 3 5

Sample Output:

3

Ý tưởng

Đây là một bài toán rất cơ bản của quy hoạch động, và các bạn hoàn toàn có thể giải quyết nó trong thời gian $O(n \times \log n)$ bằng phương pháp Tìm kiếm nhị phân. Tuy nhiên, ở bài viết này tôi sẽ giới thiệu cách giải bài toán này bằng Cây phân đoạn. Tuy nhiên, chúng ta sẽ cần một kĩ thuật bổ trợ, đó là Rời rạc hóa.

Phương pháp rời rạc hóa

Rời rạc hóa là một lĩnh vực lớn có đối tượng nghiên cứu là các tập hợp rời rạc trong khoa học máy tính. Ứng dụng của của phương pháp rất lớn và thường được sử dụng trong rất nhiều kỳ thi lớn.

Khi lập trình, phương pháp rời rạc hóa thường được gọi là "nén số". Thật vậy, đúng như tên gọi, bản chất của phương pháp ta hiểu nôm na là đưa các vùng dữ liệu lớn về vùng dữ liệu nhỏ để dễ xử lý, sao cho vẫn thỏa mãn yêu cầu của bài toán đặt ra.

Kỹ thuật bổ trợ trong phương pháp này là đánh lại số thứ tự hay còn được gọi là nén số, được thực hiện như sau: Giả sử có một mảng $A$ gồm $n$ phần tử với giá trị thuộc đoạn $[-10^9, 10^9]$ (có thể lớn hơn nữa), ta sẽ "nén" nó về một mảng nhỏ hơn, có giá trị thuộc tập $[1, n]$ nhưng vẫn đảm bảo quan hệ lớn - bé của các phần tử trong mảng như ban đầu.

Lấy ví dụ, mảng $A = [100, 100, 2000, 1500, 900000]$. Ta sẽ nén nó về một mảng $B=[1, 1, 3, 2, 4],$ vẫn đảm bảo tương quan lớn - nhỏ giữa các phần tử.

Cách thực hiện như sau:

• Sử dụng thêm mảng $B$ là một mảng chứa các bản ghi gồm hai trường: Một trường lưu giá trị $a_i$ tương ứng trên mảng $A \ (val)$ và một trường lưu vị trí $i \ (pos)$.
• Sắp xếp lại mảng $B$ dựa trên trường giá trị $val$.
• Khởi tạo một biến $d = 0$ - đây chính là các giá trị số được nén. Sau đó duyệt qua từng phần tử $b_i$ trên mảng $B,$ nếu $b_i.val \ne b_{i - 1}.val$ thì cập nhật tăng $d$ thêm $1$ đơn vị, ngược lại thì giữ nguyên $d$.
• Gán $a_{b_i.pos} = d$ để có giá trị nén trên mảng $A$.

void discretizing(int n, vector < int > &a)
{
    // Sử dụng kiểu pair để thay cho bản ghi gồm hai trường.
    vector < pair < int, int > > b(n + 1);
    for (int i = 1; i <= n; ++i)
        b[i] = {a[i], i};

    sort(b.begin() + 1, b.end());
		
    int d = 1;
    a[b[1].second] = d;
	
    for (int i = 2; i <= n; ++i)
        a[b[i].second] = (b[i].first != b[i - 1].first) ? ++d : d;
}

Sử dụng Cây phân đoạn để giải bài toán LIS

Sau khi đã rời rạc hóa mảng $A$, ta gọi $dp[i]$ là độ dài dãy con tăng dài nhất kết thúc tại phần tử $a_i$.

Công thức truy hồi dĩ nhiên rất đơn giản:

$$dp[i] = \text{max}(dp[j]) + 1; \text{nếu } a_j \in [1, a_i - 1]$$

Nhìn vào công thức trên, có thể thấy các $dp[i]$ được cập nhật từ những $dp[j]$ mà có phần tử kết thúc $a_j$ thuộc một đoạn cố định là $[1, a_i - 1]$. Nói cách khác, nếu coi các giá trị của mảng $A$ như một dãy các chỉ số từ $1$ tới $n$ và gán cho mỗi chỉ số một giá trị $dp$ tương ứng của nó, thì việc tính công thức truy hồi sẽ trở thành tìm giá trị lớn nhất trên một đoạn chỉ số liên tiếp.

Từ đây, ta có phương pháp sử dụng Cây phân đoạn như sau:

• Dựng một cây phân đoạn với các chỉ số thể hiện các giá trị trên mảng $A$. Chẳng hạn $st[5]$ sẽ đại diện cho giá trị $dp[i]$ thỏa mãn $a_i = 5$. Cây phân đoạn này sẽ lưu $dp[i]$ lớn nhất của các dãy con tăng dài nhất kết thúc tại phần tử có giá trị $a_i$.
• Mỗi khi cần tính một $dp[i],$ ta sẽ lấy giá trị $dp[j]$ lớn nhất mà có phần tử kết thúc $a_j \in [1, a_i - 1]$ dựa vào cây phân đoạn.
• Sau khi tính xong $dp[i],$ ta cập nhật giá trị $dp[i]$ vào vị trí $a_i$ trên cây.

Như vậy ta thu được thuật toán có độ phức tạp $O(n \times \log n)$.

Cài đặt

#include <bits/stdc++.h>
#define int long long

using namespace std;

void enter(int &n, vector < int > &a, vector < pair < int, int > > &b)
{
    cin >> n;
    
    a.resize(n + 1);
    b.resize(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        b[i] = {a[i], i};
    }
}

// Rời rạc hóa mảng A.
void discretizing(int n, vector < int > &a, vector < pair < int, int > > &b)
{
    sort(b.begin() + 1, b.end());
		
    int d = 1;
    a[b[1].second] = d;
	
    for (int i = 2; i <= n; ++i)
        a[b[i].second] = (b[i].first != b[i - 1].first) ? ++d : d;
}

// Cập nhật lên cây phân đoạn ở vị trí pos giá trị mới là val.
void update(int id, int u, int v, int pos, int val, vector < int > &st)
{
    if (v < pos || u > pos)    
        return;
    
    if (u == v && v == pos)
    {
        st[id] = val;
        return;
    }
    
    int mid = (u + v) >> 1;
    update(2 * id, u, mid, pos, val, st);
    update(2 * id + 1, mid + 1, v, pos, val, st);
    
    st[id] = max(st[2 * id], st[2 * id + 1]);
}

// Lấy giá trị lớn nhất trên đoạn [l, r] của cây phân đoạn.
int get(int id, int u, int v, int l, int r, vector < int > &st)
{
    if (u > r || v < l)
        return 0;
    
    if (u >= l && v <= r)
        return st[id];
    
    int mid = (u + v) >> 1;
    int get1 = get(2 * id, u, mid, l, r, st);
    int get2 = get(2 * id + 1, mid + 1, v, l, r, st);
    
    return max(get1, get2);
}

void solution(int n, vector < int > &a, vector < pair < int, int > > &b)
{
    discretizing(n, a, b);
    
    // Tính toán quy hoạch động dựa trên cây phân đoạn.
    int res = 0;
    vector < int > dp(n + 1), st(4 * n + 1); 
    for (int i = 1; i <= n; ++i)
    {
        dp[i] = get(1, 1, n, 1, a[i] - 1, st) + 1;
        res = max(res, dp[i]);
        update(1, 1, n, a[i], dp[i], st);
    }
    
    cout << res;
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    vector < int > a;
    vector < pair < int, int > > b;
        
    enter(n, a, b);
    solution(n, a, b);
    
    return 0;
}

Bài toán 2: Lắp radars

Đề bài

HN là một giám đốc của một công ty kỹ thuật số truyền hình, anh đang có kế hoạch triển khai hệ thống radars trên con đường chính của thành phố ABZ. Hiện tại, anh đang có trong tay một danh sách các địa điểm có thể cài đặt các radars, các địa điểm này được sắp xếp theo thứ tự không giảm, mỗi radar được lắp đặt sẽ cho công ty của anh một giá trị lợi nhuận không nhỏ. Để đảm bảo các radars không bị ảnh hưởng tới sóng thu phát của nhau thì khoảng cách giữa hai radar được lắp đặt không thể ít hơn $k$. Lấy ví dụ, với danh sách lắp đặt hệ thống tại vị trí $1,2$ và $3$ và lợi nhuận tương ứng là $2,4$ và $3$. Nếu $k=2,$ thì khi lựa chọn các radar ở vị trí $1$ và $3$ để lắp đặt sẽ cho ra lợi nhuận bằng $5$.

Yêu cầu: Cho trước danh sách các địa điểm và lợi nhuận, hãy giúp HN lựa chọn các địa điểm lắp đặt các hệ thống radar để lợi nhuận thu được là tối đa?

Input:

• Dòng đầu tiên chứa số nguyên dương $T$ – số lượng test cases.
• $T$ nhóm dòng tiếp theo, mỗi nhóm dòng chứa một tes case, cấu trúc như sau:
  • Dòng đầu tiên chứa hai số nguyên dương $n$ và $k$ – số lượng hệ thống radars và giới hạn khoảng cách tối thiểu giữa hai radar liên tiếp được chọn.
  • Dòng tiếp theo chứa $n$ số nguyên dương $a_i \ (1 \le i \le n)$ phân tách nhau bởi dấu cách – vị trí của radar thứ $i$.
  • Dòng cuối cùng chứa $n$ số nguyên dương $b_i \ (1 \le i \le n)$ phân tách nhau bởi dấu cách – lợi nhuận thu được nếu lắp đặt hệ thống radar thứ $i$.

Ràng buộc:

• $1≤T≤10$.
• $1≤n,k≤10^6$.
• $1≤a_i≤10^6;∀i:1≤i≤n$.
• $1≤b_i≤10^3;∀i:1≤i≤n$.

Output:

• Trên $T$ dòng, dòng thứ $i$ đưa ra một số nguyên duy nhất là tổng lợi nhuận lớn nhất thu được ở test case thứ $i$.

Sample Input:

3
2 1
1 2
3 2
3 2
1 2 3
2 4 3
5 5
1 5 10 15 17
5 20 10 15 25

Sample Output:

5
5
55

Ý tưởng

Đây là một bài toán quy hoạch động đơn giản. Gọi $dp[i]$ là lợi nhuận lớn nhất thu được khi đặt các radars từ vị trí $1$ tới vị trí $a_i$. Công thức quy hoạch động rất đơn giản, ta xét hai trường hợp:

• Radar cuối cùng đặt tại vị trí $a_i,$ thì các radars khác chỉ được phép đặt từ vị trí $1$ tới $a_i - K$. Khi đó lợi nhuận thu được là:

  $$\text{max}\big(dp[j] + b_i\big); \forall j: 1 \le j \le a[i] - k$$

• Không đặt radar nào vào vị trí $a_i$ thì lợi nhuận thu được là $dp[i - 1]$.

Tất nhiên vì ta cần lấy giá trị lợi nhuận lớn nhất, nên $dp[i]$ sẽ bằng giá trị lớn nhất trong hai trường hợp trên. Nhưng làm thế nào để tính toán được giá trị $\text{max}\big(dp[j] + b_i\big)?$ Nếu như duyệt lại các giá trị $j$ thì độ phức tạp sẽ lên tới $O(10^6),$ kết hợp với việc duyệt $i$ từ $1$ tới $n$ thì sẽ không thể vượt qua được test cases. Giải pháp tốt hơn sẽ là sử dụng cây phân đoạn.

Ta sử dụng một cây phân đoạn để kiểm soát giá trị lớn nhất của các $dp[i]$. Cụ thể hơn, cây phân đoạn sẽ kiểm soát các tọa độ từ $1$ tới $\text{max}(a_i),$ và giá trị của các nút trên cây sẽ là giá trị $dp$ lớn nhất của tọa độ mà nút đó quản lý.

Mỗi khi tính toán xong một $dp[i],$ ta update giá trị $dp[i]$ vào vị trí $a_i$ trên cây phân đoạn, như vậy thao tác lấy kết quả sẽ nhanh hơn rất nhiều.

Độ phức tạp thuật toán khi đó sẽ đạt được là $O(n \times \log a_i)$.

Cài đặt

Cần lưu ý một số điểm sau:

• Cây phân đoạn kiểm soát các tọa độ $a_i,$ do đó kích thước tối đa của nó phải là $4 \times \text{max}(a_i),$ chứ không phải $4 \times n$ như ở các bài toán thường thấy.
• Khi update lên cây phân đoạn, vị trí cần update là vị trí $a_i$ chứ không phải vị trí $i$. Đây là những thao tác dễ nhầm lẫn nên các bạn cần hết sức cẩn thận.

#include <bits/stdc++.h>
#define int long long

using namespace std;

void enter_testcase(int &n, int &k, vector < int > &a, vector < int > &b)
{
    cin >> n >> k;

    a.resize(n + 1);
    b.resize(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
        cin >> b[i];
}

void update(int id, int u, int v, int pos, int val, vector < int > &st)
{
    if (v < pos || u > pos)
        return;

    if (u == v)
    {
        st[id] = val;
        return;
    }

    int mid = (u + v) >> 1;
    update(2 * id, u, mid, pos, val, st);
    update(2 * id + 1, mid + 1, v, pos, val, st);

    st[id] = max(st[2 * id], st[2 * id + 1]);
}

int get(int id, int u, int v, int l, int r, vector < int > &st)
{
    if (u > r || v < l)
        return 0;

    if (u >= l && v <= r)
        return st[id];

    int mid = (u + v) >> 1;
    int get1 = get(2 * id, u, mid, l, r, st);
    int get2 = get(2 * id + 1, mid + 1, v, l, r, st);

    return max(get1, get2);
}

void solution(int n, int k, vector < int > &a, vector < int > &b)
{
    int maxa = *max_element(a.begin() + 1, a.end());
    vector < int > dp(n + 1), st(4 * maxa + 1);

    for (int i = 1; i <= n; ++i)
    {
        dp[i] = max(dp[i - 1], get(1, 1, maxa, 1, a[i] - k, st) + b[i]);
        update(1, 1, maxa, a[i], dp[i], st);
    }

    cout << dp[n] << endl;
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int ntest;
    cin >> ntest;

    while (ntest--)
    {
        int n, k;
        vector < int > a, b;

        enter_testcase(n, k, a, b);
        solution(n, k, a, b);
    }

    return 0;
}

Bài toán 3: Dãy con liên tiếp

Đề bài

Cho dãy số nguyên $A$ gồm $n$ phần tử và một số nguyên $p$. Một dãy con liên tiếp của dãy số là một cách chọn ra các phần tử liên tiếp nhau trong dãy và loại bỏ các phần tử còn lại.

Yêu cầu: Đếm số lượng dãy con liên tiếp khác nhau có trung bình cộng không nhỏ hơn $p?$ Hai dãy con liên tiếp được gọi là khác nhau nếu như chúng có phần tử đầu hoặc cuối dãy là khác nhau.

Input:

• Dòng đầu tiên chứa hai số nguyên dương $n$ và $p$.
• Dòng thứ hai chứa $n$ số nguyên dương $a_1, a_2, \dots, a_n$ phân tách nhau bởi dấu cách.

Ràng buộc:

• $1 \le n \le 2 \times 10^5$.
• $1 \le p \le 10^9$.
• $1 \le a_i \le 10^9; \forall i: 1 \le i \le n$.

Output:

• In ra số lượng dãy con có trung bình cộng không nhỏ hơn $p$ tìm được.

Sample Input:

3 3
1 4 2

Sample Output:

2

Ý tưởng

Với giá trị $n$ nhỏ, ta có thể sử dụng hai vòng lặp để duyệt mọi dãy con liên tiếp, tính trung bình cộng và đếm số dãy thỏa mãn yêu cầu đề bài.

Độ phức tạp của cách làm trên là $O(n^2),$ không đủ tốt với ràng buộc $n \le 2 \times 10^5$. Ta sẽ phải cải tiến thuật toán.

Không mất tính tổng quát, giả sử $a_i = a_i - p; \forall i: 1 \le i \le n$ thì các dãy con liên tiếp có trung bình cộng lớn hơn hoặc bằng $p$ sẽ trở thành các dãy con liên tiếp có tổng lớn hơn hoặc bằng $0$.

Xây dựng mảng tổng tiền tố của dãy $A$ sau khi xử lý $a_i = a_i - p; \forall i: 1 \le i \le n$. Với mỗi $sum[i],$ ta lưu hai thông tin là tổng các số từ $a_1$ tới $a_i$ và vị trí $i$ của tổng đó, sau đó sắp xếp lại các $sum[i]$ theo thông tin thứ nhất. Giả sử hai thông tin lần lượt là $sum[i].s$ và $sum[i].pos$.

Dễ thấy, sau khi sắp xếp lại, mỗi $sum[i]$ đều có thể ghép với mọi $sum[j] \ (j = 0...i - 1)$ để tạo thành tổng dương. Bây giờ cần đếm xem trong các $sum[j]$ đó, có những vị trí nào thỏa mãn $sum[j].pos < sum[i].pos$ thì mới tạo thành một đoạn con hợp lệ (vị trí sau trừ đi vị trí trước trên mảng tổng tiền tố).

Sử dụng một cây phân đoạn, với mục đích để đếm số lượng giá trị $x$ xuất hiện trong đoạn $[l, r] \ (l \le x \le r)$. Khi xét tới $sum[i],$ số lượng vị trí ghép được với $sum[i]$ là số lượng giá trị $sum[j]$ có $sum[j].pos \in [0...i - 1]$ đã xuất hiện trước đó. Cây phân đoạn dùng để tính tổng đoạn $[0...i - 1]$ này. Sau mỗi lần tính, cập nhật vị trí $sum[i].pos$ tăng thêm $1$ trên cây để chuẩn bị cho các vị trí tiếp theo.

Độ phức tạp: $O(n \times \log n)$.

Cài đặt

#include <bits/stdc++.h>
#define int long long 

using namespace std;

const int maxn = 1e6;
int st[maxn];

void enter(int &n, int &p, vector < int > &a, vector < pair < int, int > > &sum)
{
    cin >> n >> p;
    
    a.resize(n + 1);
    sum.resize(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        a[i] -= p;
        sum[i].first = sum[i - 1].first + a[i];
        sum[i].second = i;
    }
}

void update(int id, int u, int v, int pos, int value, int st[])
{
    if (u > pos || v < pos)
        return;
    
    if (u == v && v == pos)
    {
        st[id] += 1;
        return;
    }
    
    int mid = (u + v) >> 1;
    update(id * 2, u, mid, pos, value, st);
    update(id * 2 + 1, mid + 1, v, pos, value, st);
    
    st[id] = st[id * 2] + st[id * 2 + 1];
}

int get(int id, int u, int v, int l, int r, int st[])
{
    if (u > r || v < l) 
        return 0;
    
    if (u >= l && v <= r)
        return st[id];
    
    int mid = (u + v) >> 1;
    return get(id * 2, u, mid, l, r, st) + get(id * 2 + 1, mid + 1, v, l, r, st);
}

void solution(int &n, vector < int > &a, vector < pair < int, int > > &sum)
{
    sort(sum.begin() + 1, sum.end());
    
    int res = 0;
    for (int j = 1; j <= n; ++j)
    {
        res += (sum[j].first >= 0);
        res += get(1, 1, n, 1, sum[j].second - 1, st);
        
        update(1, 1, n, sum[j].second, 1, st);
    }
    
    cout << res;
}

main()
{
    int n, p;
    vector < int > a;
    vector < pair < int, int > > sum;
    
    enter(n, p, a, sum);
    solution(n, a, sum);
    
    return 0;
}

Bài toán 4: Dãy số hình nón

Đề bài

Cho một dãy số $A$ gồm $N$ phần tử $a_1, a_2,..., a_N$. Một dãy con (không liên tiếp) của dãy A là một cách chọn ra $K$ phần tử có chỉ số $i_1, i_2,...,i_K$ bất kỳ trong dãy. Dãy con đó được gọi là dãy con hình nón độ dài $K$ nếu như tồn tại một vị trí $i_P \ (i_1 \le i_P \le i_K)$ sao cho:

$$a_{i_1} < a_{i_2} < \cdots < a_{i_P - 1} < a_{i_P} > a_{i_P + 1} > a_{i_P + 2} > \cdots > a_{i_K}$$

Yêu cầu: Hãy tìm dãy con hình nón có tổng các chữ số của các số trong dãy là lớn nhất có thể?

Input:

• Dòng đầu tiên chứa số nguyên dương $N$.
• Dòng thứ hai chứa $N$ số nguyên dương $a_1, a_2,..., a_N,$ phân tách nhau bởi dấu cách.

Ràng buộc:

• $1 \le N \le 10^5$.
• $1 \le a_i \le 10^9; \forall i: 1 \le i \le N$.

Subtasks:

• Subtask $1$ ($30\%$ số điểm): $N \le 20$.
• Subtask $2$ ($30\%$ số điểm): $20 < N \le 2000$.
• Subtask $3$ ($40\%$ số điểm): Không có ràng buộc gì thêm.

Output:

• Số nguyên duy nhất là tổng chữ số của tất cả các số trong dãy con tìm được.

Sample Input:

10
1 10 11 12 8 3 9 6 7 3

Sample Output:

28

Giải thích:

Dãy số tìm được là: $\{1, 8, 9, 7, 3\}$.

Ý tưởng

Subtask 1

Dùng quay lui hoặc duyệt bit để thử chọn tất cả các dãy con và kiểm tra tính chất hình nón của chúng, sau đó tính tổng các chữ số của dãy đó.

Subtask 2

Ý tưởng của subtask này được phát triển từ bài toán tìm dãy con tăng dài nhất cơ bản. Ứng với mỗi $a_i,$ đặt \text{dp_left}[i] và \text{dp_right}[i] lần lượt là độ dài dãy con tăng có tổng chữ số lớn nhất kết thúc tại vị trí $i$ nhưng theo chiều từ $1$ tới $i$ và từ $N$ về $i$. Gọi luôn $D(a_i)$ là hàm tính tổng các chữ số của $a_i$ (cần phải khởi tạo trước), ta có công thức quy hoạch động:

\begin{cases}\text{dp_left}[i] = \text{max}\big(\text{dp_left}[j] + D(a_i)\big), \forall j: 1 \le j < i. \\ \text{dp_right}[i] = \text{max}\big(\text{dp_right}[j] + D(a_i)\big), \forall j: i < j \le N. \end{cases}

Sử dụng hai vòng lặp với độ phức tạp $O(N^2),$ ta xây dựng được hai mảng \text{dp_left, dp_right} dựa trên quy hoạch động. Để tìm kết quả, ta nhận xét như sau: Dãy hình nón có thể xảy ra ở một trong hai trường hợp:

• Dãy kết thúc tại $i$ chỉ tăng dần hoặc giảm dần (nghĩa là $a_i$ hoặc là phần tử cuối cùng, hoặc là phần tử đầu tiên). Trường hợp này kết quả bằng \text{max}(\text{dp_left}[i],\text{dp_right}[i]).
• Dãy hình nón có $a_i$ là phần tử ở đỉnh dãy số, hai bên giảm dần xuống. Trường hợp này kết quả bằng: \text{max}\big(\text{dp_left}[i] + \text{dp_right}[i] - D(a_i)\big), do $a_i$ được tính hai lần trong cả hai giá trị $dp$.
• Kết quả cuối cùng sẽ bằng giá trị lớn nhất trong cả hai cách chọn trên.

Subtask 3

Vẫn dựa vào ý tưởng trên, tuy nhiên vì $N \le 10^5$ nên việc cập nhật các bảng phương án dựa trên vị trí không thể thỏa mãn ràng buộc thời gian. Ta sẽ thay đổi một chút:

• \text{dp_left}[i]: Dãy con tăng có tổng chữ số lớn nhất kết thúc tại giá trị $a_i$ tính từ $1$ tới $i$.
• \text{dp_right}[i]: Dãy con tăng có tổng chữ số lớn nhất kết thúc tại giá trị $a_i$ tính từ $N$ về $i$.

Nhận thấy, các \text{dp_left}[i] sẽ được cập nhật từ những \text{dp_left}[j] có $1 \le a_j < a_i,$ tương tự với các \text{dp_right}[i]. Ta xây dựng một Segment Tree để tính giá trị lớn nhất trong tất cả các \text{dp_left}[j], nhưng vị trí của các nodes trên cây sẽ kiểm soát những giá trị $a_j$ thay vì vị trí $j$ (các bạn xem lại phần bài toán cơ bản của cây phân đoạn tôi đã viết ở bài viết trước). Xây dựng hoàn toàn tương tự với mảng \text{dp_right}[i]. Để cây phân đoạn có thể kiểm soát được các giá trị trong dãy số ban đầu, ta cần sử dụng thêm kĩ thuật rời rạc hóa (giống như ở bài toán 1), để nén các số trong dãy về giá trị không vượt quá $N$. Tới đây, ta có công thức quy hoạch động:

\begin{cases}\text{dp_left}[i] = \text{get_max}\big(ST[a_j] + D(a_i)\big), \forall a_j: 1 \le a_j < a_i. \\ \text{dp_right}[i] = \text{get_max}\big(ST[a_j] + D(a_i)\big), \forall a_j: 1 \le a_j < a_i. \end{cases}

Để tính \text{dp_left}[i], ta duyệt từ trái qua phải, còn \text{dp_right}[i] thì duyệt từ phải qua trái. Mỗi khi tính xong một giá trị $dp[i]$ thì dùng thao tác update để cập nhật giá trị của $dp[i]$ lên node thứ $a_i$ trên Segment Tree. Còn cách lấy kết quả cuối cùng vẫn giống như ở subtask 2. Như vậy ta xây dựng được giải thuật $O(N.\log_2N)$.

Cài đặt

#include <bits/stdc++.h>
#define task "CONE."
#define int long long

using namespace std;

const int maxn = 1e5 + 10;
int N, digitize_value, st[4 * maxn];
pair < int, int > a[maxn], b[maxn], dp[maxn];
unordered_map < int, int > new_value;

int get_digit_sum(int N) // Calculate total of the digits of N.
{
    int digit_sum = 0;
    while (N)
        digit_sum += (N % 10), N /= 10;

    return digit_sum;
}

void enter()
{
    cin >> N;

    // Here let a[i].first is the value of a[i], and a[i].second is the total of digits of a[i].
    for (int i = 1; i <= N; ++i)
    {
        cin >> a[i].first;
        a[i].second = get_digit_sum(a[i].first);
        b[i] = {a[i].first, i};
    }
}

// Digitize the array such that every a[i] becomes less or equal to N.
void digitizing()
{
    sort(b + 1, b + 1 + N);

    for (int i = 1; i <= N; ++i)
        a[b[i].second].first = (b[i].first != b[i - 1].first) ? ++digitize_value : digitize_value;
}

// Update a pos on interval tree, set it by value and build tree.
void update(int id, int u, int v, int pos, int val) 
{
    if (u > pos || v < pos)
        return;

    if (u == v)
    {
        st[id] = val;
        return;
    }

    int mid = (u + v) >> 1;
    update(id * 2, u, mid, pos, val);
    update(id * 2 + 1, mid + 1, v, pos, val);

    st[id] = max(st[id * 2], st[id * 2 + 1]);
}

// Use IT to get the maximum value on range [l, r] (dp[i] will be 
// updated by dp[j] which have 1 <= a[j] < a[i]).
int get(int id, int u, int v, int l, int r)
{
    if (u > r || v < l)
        return 0;

    if (u >= l && v <= r)
        return st[id];

    int mid = (u + v) >> 1;
    return (max(get(id * 2, u, mid, l, r), get(id * 2 + 1, mid + 1, v, l, r)));
}

void solution()
{
    for (int i = 1; i <= N; ++i)
    {
        dp[i].first = get(1, 1, digitize_value, 1, a[i].first - 1) + a[i].second;
        update(1, 1, digitize_value, a[i].first, dp[i].first);
    }
    memset(st, 0, sizeof st);
    for (int i = N; i >= 1; --i)
    {
        dp[i].second = get(1, 1, digitize_value, 1, a[i].first - 1) + a[i].second;
        update(1, 1, digitize_value, a[i].first, dp[i].second);
    }

    // Find last result.
    int res = 0;
    for (int i = 1; i <= N; ++i)
        res = max(res, max(dp[i].first, dp[i].second));
    for (int i = 1; i <= N; ++i)
        res = max(res, dp[i].first + dp[i].second - a[i].second);

    cout << res;
}

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

    enter();
    digitizing();
    solution();

    return 0;
}

Tài liệu tham khảo

• VNOI Segment Tree Problems.
• https://vnoi.info/wiki/algo/data-structures/segment-tree-basic.md
• Codeforces - Segment Tree Problems.
• https://cp-algorithms.com/data_structures/segment_tree.html