10.8K 806 127

Đã đăng vào thg 2 5, 8:00 SA 15 phút đọc

Cây phân đoạn (phần 3) - Lazy Propagation

MayFest2024

I. Đặt vấn đề

Trong series bài viết trước về Cây phân đoạn, tôi đã giới thiệu tới các bạn những vấn đề cơ bản về cấu trúc dữ liệu này, bao gồm:

Thao tác xây dựng.
Thao tác cập nhật.
Thao tác lấy kết quả.
Một số bài toán cơ bản ứng dụng Cây phân đoạn.

Tuy nhiên, trong các bài viết trước đây, các thao tác cập nhật trên dãy số trong các bài toán đều chỉ là cập nhật một phần tử. Sẽ ra sao nếu như thao tác cập nhật là cập nhật lại một đoạn phần tử, ví dụ như bài toán dưới đây:

Cho một mảng số nguyên $A$ gồm $n$ phần tử. Bạn cần thực hiện hai truy vấn trên mảng:

Loại 1 có dạng $1 \ l \ r \ val$ : Tăng giá trị của các phần tử từ vị trí $l$ tới vị trí $r$ trên mảng lên $val$ đơn vị.
Loại 2 có dạng $2 \ l \ r$ : Đưa ra giá trị của phần tử nhỏ nhất trong đoạn vị trí $[l, r]$ của dãy số.

Input:

Dòng đầu tiên chứa số nguyên dương $n$ - độ dài dãy số.
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.
Dòng thứ ba chứa số nguyên dương $q$ - số lượng truy vấn.
$Q$ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương thể hiện một truy vấn.

Ràng buộc:

$1 \le n, Q \le 10^5$ .
$|a_i| \le 10^9; \forall i: 1 \le i \le n$ .
$|val| \le 10^9$ .
$1 \le l \le r \le n$ .

Output:

Ứng với mỗi truy vấn loại $2,$ in ra đáp án trên một dòng.

Sample Input:

Sample Output:

8
7
9

II. Kĩ thuật Cập nhật lười (Lazy Propagation)

Với bài toán minh họa đã nêu ở trên, nếu như ta sử dụng thao tác update với tất cả các phần tử trong đoạn $[x, y]$ rổi lại cập nhật lên cây, thì độ phức tạp của thuật toán có thể sẽ rất lớn, bởi vì đoạn $[x, y]$ có thể chứa tối đa $n$ phần tử, dẫn đến việc mỗi thao tác update có thể mất tới $O(n \log n)$ .

Cập nhật lười (Lazy Propagation, Lazy Update) là một kĩ thuật được sử dụng trong Segment Tree để giảm độ phức tạp của Segment Tree với các truy vấn cập nhật đoạn dạng trên.

Ý tưởng chung

Thay vì cập nhật từng phần tử với mỗi thao tác update đoạn $[l, r],$ thì ta sẽ chỉ cập nhật các nút quản lý các đoạn lớn nhất (hay các nút gần gốc của cây nhất) mà tổng hợp của các đoạn đó đúng bằng đoạn $[l, r]$ . Sau đó, ta lưu lại một giá trị ở các nút đó - gọi là giá trị lazy update - dùng để đánh dấu lại rằng các nút thuộc đoạn này đều sẽ phải được cập nhật bằng một giá trị tương ứng. Những nút con sẽ chỉ được cập nhật lại chính xác khi thực sự cần thiết.

Lấy ví dụ, với mảng $A = [9, 2, 6, 3, 1, 5, 7],$ và ta cần cập nhật đoạn $[1, 6]$ . Cây phân đoạn giá trị nhỏ nhất biểu diễn mảng như hình dưới đây:

</center>

Thay vì đi vào cập nhật tất cả các nút chứa các phần tử thuộc đoạn $[1, 6],$ thì ta sẽ chỉ cập nhật hai nút lớn nhất là $[1, 4]$ và $[5, 6]$ $\big($hợp nhất lại vừa đủ bằng đoạn $[1, 6]\big)$ . Còn các nút quản lý các đoạn $[1,2], [3,4], [1,1], [2,2], [3,3], [4,4], [5,5]$ và $[6,6]$ thì sẽ chỉ cập nhật lại khi thực sự cần thiết.

Áp dụng vào bài toán

Trở lại bài toán minh họa, ban đầu ta vẫn xây dựng cây phân đoạn quản lý mảng ban đầu bằng thao tác Xây dựng cây.

Truy vấn loại 2 không có gì đáng lưu ý, nó vẫn là thao tác Lấy giá trị như ở các bài toán cơ bản.

Với truy vấn loại 1, ta cần cập nhật giá trị cho đoạn $[u, v]$ . Giả sử $f(id)$ là giá trị lớn nhất trong đoạn mà nút $id$ quản lý. Trong lúc cập nhật, muốn việc cập nhật thực hiện trong thời gian không quá $O(\log n),$ thì khi xét đến một nút $id$ quản lý đoạn $[l, r]$ mà đoạn $[l, r]$ nằm hoàn toàn trong đoạn $[u, v],$ ta sẽ không đệ quy vào các nút con của nó nữa (để tránh phải xét toàn bộ các nút quản lý các phần tử của đoạn $[u, v]$ ).

Kĩ thuật Lazy Propagation diễn ra như sau:

Mỗi nút của Segment Tree sẽ lưu thêm một giá trị $lazy[id]$ với ý nghĩa là tất cả các phần tử trong đoạn $[l,r]$ mà nút $id$ quản lý đều được tăng thêm một giá trị là $lazy[id]$ . Nói cách khác, nó sẽ lưu trữ các giá trị cần cập nhật của mỗi nút.
Ban đầu, ta khởi tạo tất cả các phần tử của mảng $lazy[]$ bằng $0$ . Nếu $lazy[id]=0$ có nghĩa là không có cập nhật nào đang chờ được xử lý trên nút $id$ trong cây phân đoạn. Ngược lại, nếu $lazy[id] \ne 0$ nghĩa là ta cần cập nhật giá trị của nút $id$ theo $lazy[id]$ trước khi thực hiện bất kỳ thao tác nào với nút đó (việc cập nhật này tùy vào mục đích của cây; ví dụ như trong bài toán trên, giá trị của nút $id$ sẽ được tăng thêm $lazy[id]$ ).
Nếu nút $id$ đang xét còn có giá trị được thêm vào chưa xét đến (từ các truy vấn cập nhật xảy ra trước đó, mà chưa được cập nhật hết), ta buộc phải cập nhật nó trước khi lấy giá trị hoặc tiếp tục đệ quy sâu hơn. Sau khi cập nhật xong nút $id,$ ta phải đẩy giá trị $lazy$ ở nút $id$ xuống các con của nó để tiếp tục cập nhật và đặt lại $lazy$ của nút $id$ về $0$ .

Để làm được những điều trên, ở đầu các hàm get() và update() ta thực hiện các thao tác sau:

st[id] += lazy[id]; - cập nhật giá trị nút $id$ theo $lazy[id]$ .
Nếu nút $id$ $i d$ không phải là lá thì ta đẩy giá trị $lazy$ $l a zy$ xuống các con của nó bằng các câu lệnh dưới đây:
- lazy[2 * id] += lazy[id];.
- lazy[2 * id + 1] += lazy[id];.
Gán lại giá trị lazy ở nút $id$ $i d$ về $0$ $0$ để tránh mỗi phần tử của dãy bị tăng lên nhiều lần do lời gọi đệ quy:
- lazy[id] = 0.

Bây giờ, để cập nhật đoạn, ta thực hiện tương tự như ở thao tác lấy giá trị, là xác định tập hợp ít nút nhất sao cho hợp tất cả các phạm vi mà các nút đó quản lí đúng bằng đoạn cần cập nhật. Khi đó, ta sửa lại giá trị của các nút thuộc tập hợp này và lưu lại giá trị cần cập nhật vào lazy tương ứng với các nút con của chúng.

Cài đặt

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

using namespace std;

void build_tree(int id, int u, int v, vector < int > &a, vector < int > &st) 
{
    if (u == v) 
    {
        st[id] = a[u];
        return;
    }
	
    int mid = (u + v) >> 1;
    build_tree(2 * id, u, mid, a, st);
    build_tree(2 * id + 1, mid + 1, v, a, st);
	
    st[id] = max(st[2 * id], st[2 * id + 1]);
}

// Cập nhật nút đang xét và đẩy giá trị lazy xuống các nút con
void lazy_update(int id, int u, int v, vector < int > &st, vector < int > &lazy) 
{
    if (!lazy[id]) 
        return;
	
    st[id] += lazy[id];
    
    // Nếu id không phải là nút lá thì đẩy giá trị lazy xuống các nút con.
    if (u != v)
    {
        lazy[2 * id] += lazy[id];
        lazy[2 * id + 1] += lazy[id];
    }
    
    lazy[id] = 0;
}

// Thao tác cập nhật kết hợp với Lazy Propagation.
void update(int id, int u, int v, int l, int r, int val, 
            vector < int > &st, vector < int > &lazy) 
{
    lazy_update(id, u, v, st, lazy);
	
    if (u > r || v < l) 
        return;
	
    // Khi cài đặt, ta LUÔN ĐẢM BẢO giá trị của nút được cập nhật 
    // ĐỒNG THỜI với giá trị Lazy Propagation. Như vậy sẽ tránh sai sót.
    if (u >= l && v <= r) 
    {    
        lazy[id] += val;
        lazy_update(id, u, v, st, lazy);
		
        return;
    }
	
    int mid = (u + v) >> 1;
    update(2 * id, u, mid, l, r, val, st, lazy);
    update(2 * id + 1, mid + 1, v, l, r, val, st, lazy);
	
    st[id] = max(st[2 * id], st[2 * id + 1]);
}

// Thao tác lấy giá trị cơ bản, không có gì đáng chú ý.
long long get(int id, int u, int v, int l, int r, 
              vector < int > &st, vector < int > &lazy) 
{
    lazy_update(id, u, v, st, lazy);
	
    if (u > r || v < l) 
        return LLONG_MIN;
	
    if (u >= l && v <= r) 
        return st[id];

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

int main() 
{
    int n;
    cin >> n;
	
    vector < int > a(n + 1);
    for (int i = 1; i <= n; ++i) 
        cin >> a[i];
	
    vector < int > st(4 * n + 1), lazy(4 * n + 1);
    build_tree(1, 1, n, a, st);
    
    int q;
    cin >> q;
	
    while (q--)
    {
        int type, l, r, val;
        cin >> type >> l >> r;
		
        if (type == 1) 
        {
            cin >> val;
            update(1, 1, n, l, r, val, st, lazy);
        }
        else 
            cout << get(1, 1, n, l, r, st, lazy) << endl;
    }
}

Đánh giá

Độ phức tạp tính toán của thao tác cập nhật Lazy Propagation là $O(\log n),$ vì thế độ phức tạp tổng quát của thuật toán có thể coi là $O(q \times \log n)$ .

III. Bài toán minh họa

1. A simple task (Codeforces Round 312 Div. 2)

Đề bài

Cho chuỗi kí tự $s$ độ dài $n$ chỉ bao gồm các chữ cái tiếng Anh in thường, các kí tự được đánh số thứ tự từ $1$ tới $n$ . Bạn cần thực hiện $q$ truy vấn, mỗi truy vấn có dạng $i \ j \ k$ có nghĩa là sắp xếp chuỗi con $s_{i...j}$ theo thứ tự từ điển không giảm nếu $k = 1,$ và không tăng nếu $k = 0$ .

Yêu cầu: In ra chuỗi $s$ sau khi đã thực hiện tất cả các truy vấn?

Input:

Dòng đầu tiên chứa hai số nguyên $n$ và $q$ .
Dòng thứ hai chứa chuỗi kí tự $s$ độ dài $n$ chỉ bao gồm các chữ cái tiếng Anh in thường.
$q$ dòng cuối cùng, mỗi dòng chứa ba số nguyên $i, j, k$ thể hiện một truy vấn.

Ràng buộc:

$1 \le n \le 10^5$ .
$0 \le q \le 50000$ .
$1 \le i \le j \le n$ .
$k \in [0, 1]$ .

Output:

In ra chuỗi $s$ sau khi đã thực hiện đủ $q$ truy vấn.

Sample Input:

10 5
abacdabcda
7 10 0
5 8 1
1 4 0
3 6 0
7 10 1

Sample Output:

cbcaaaabdd

Ý tưởng

Để giải quyết bài toán này, với mỗi truy vấn ta sẽ áp dụng giải thuật Sắp xếp bằng đếm phân phối. Cụ thể, ta đếm số lần xuất hiện của các kí tự trong đoạn $[i, j];$ rồi xếp lại chúng theo thứ tự giảm hoặc tăng tùy vào việc $k = 0$ hay bằng $1$ .

Đoạn code cho ý tưởng trên có thể mô tả sơ lược như sau:

for (int it = i; it <= j; ++it)
    ++cnt[s[it] - 'a'];

// Nếu sắp xếp tăng dần thì bắt đầu từ 'a', ngược lại bắt đầu từ 'z'.
int index = (k ? 0 : 25);
for (int it = i; it <= j; ++it)
{
    // Tìm kí tự tiếp theo phù hợp để đặt vào vị trí it trong đoạn.
    while (index >= 0 && cnt[index] != 0)
        index += (k ? 1 : -1);

    // Đặt kí tự phù hợp với cách sắp xếp vào vị trí hiện tại.
    s[it] += (char) (index + 'a');
    --cnt[index];
}

Độ phức tạp của đoạn code trên là $O(n),$ và tất nhiên nó sẽ không đủ tốt với số lượng truy vấn lớn. Ta cần một cách triển khai tốt hơn cho ý tưởng này.

Để cải tiến, ta sẽ tạo ra $26$ mảng để xử lý $26$ kí tự trong bảng chữ cái tiếng Anh in thường, mỗi mảng sẽ lưu các vị trí xuất hiện của kí tự tương ứng trong chuỗi $s$ bằng các trạng thái $0$ và $1$ - tương ứng với việc kí tự không xuất hiện hoặc có xuất hiện tại vị trí tương ứng.

Lấy ví dụ, với chuỗi $s=$ dabedaba, thì kí tự a sẽ được biểu diễn bởi một mảng $[0, 1, 0, 0, 0, 1, 0, 1]$ - với các vị trí mang giá trị $1$ nghĩa là tại vị trí đó có xuất hiện kí tự a. Tương tự, kí tự b sẽ có một mảng biểu diễn là $[0,0,1,0,0,0,1,0],...$

Kế đến, mỗi mảng này sẽ được kiểm soát bởi một cây phân đoạn, cây này dùng để đếm số lần xuất hiện của từng kí tự trong đoạn $[i, j]$ ở mỗi truy vấn, sau đó sắp xếp lại chúng và cập nhật lại từng cây phân đoạn với các giá trị mới.

Lấy ví dụ, với chuỗi $s =$ dabedaba và ta đang cần sắp xếp cả chuỗi theo thứ tự từ điển tăng dần (coi như truy vấn sắp xếp cả chuỗi), thì công việc diễn ra như sau:

Đặt $cnt[i]$ là số lần xuất hiện của kí tự mang số hiệu $i$ trong chuỗi (số hiệu này được mã hóa lại từ $0$ tới $25$ ). Giá trị này tính được bằng cách lấy giá trị từ cây phân đoạn quản lý mảng trạng thái của kí tự tương ứng (cây phân đoạn xây dựng là cây phân đoạn tính tổng).

Sau khi lấy giá trị xong, trên cây phân đoạn, ta sẽ cập nhật lại tất cả phần tử của mảng tương ứng với từng kí tự bằng giá trị $0$ - để thể hiện rằng ta sẽ có một thứ tự sắp xếp mới.

Tiếp theo, ta dùng cây phân đoạn để cập nhật mảng tương ứng với kí tự a từ vị trí $1$ đến vị trí $3$ (do $cnt[$ a $]=3$ ) bằng giá trị $1$ . Rồi lại tiếp tục cập nhật mảng tương ứng với kí tự b từ vị trí $4$ đến vị trí $5$ (do $cnt[$ b $]=2$ ) bằng giá trị $1$ . Vì $cnt[$ c $]=0$ nên ta bỏ qua kí tự c. Và lại tiếp tục với kí tự d,...đến kí tự z.

Còn nếu như truy vấn yêu cầu sắp xếp giảm dần, thì ta chỉ cần xét ngược lại các kí tự từ z về a.

Để cập nhật tăng các đoạn theo cách nói trên, cần sử dụng kĩ thuật Lazy Propagation. Khác với bài toán ví dụ đã nêu ở mục I, do cây phân đoạn ở bài toán này là cây phân đoạn lấy tổng, nên mỗi khi cập nhật nút $id$ quản lí đoạn $[l,r]$ theo giá trị $lazy[id]$ thì giá trị của nút $id$ sẽ được tăng thêm $lazy[id] \times (r−l+1),$ vì khi mỗi phần tử tăng thêm $lazy[id]$ thì tổng giá trị của cả đoạn $[l,r]$ sẽ tăng thêm $lazy[id] \times (r−l+1)$ .

Cài đặt

#include <bits/stdc++.h>

using namespace std;

const int maxn = 4e5 + 10;
int cnt[30];
int st[30][4 * maxn], lazy[30][4 * maxn];

// Khởi tạo các cây phân đoạn cho các kí tự có trong chuỗi.
void build_tree(int id, int u, int v, string &s) 
{
    // Khởi tạo giá trị mảng lazy ban đầu bằng -1.
    for (int ch = 0; ch <= 25; ++ch) 
        lazy[ch][id] = -1;

    if (u == v) 
    {
        st[s[u] - 'a'][id] = 1;
        return;
    }
	
    int mid = (u + v) >> 1;
    build_tree(2 * id, u, mid, s);
    build_tree(2 * id + 1, mid + 1, v, s);
	
    for (int ch = 0; ch <= 25; ++ch)
        st[ch][id] = st[ch][2 * id] + st[ch][2 * id + 1];
}

void lazy_update(int id, int u, int v, int ch) 
{
    if (lazy[ch][id] == -1) 
        return;
	
    st[ch][id] = lazy[ch][id] * (v - u + 1);
	
    if (u != v)
    {    
        // Vì là thao tác gán giá trị chứ KHÔNG phải là tăng thêm một lượng
        // nên lazy của nút con sẽ gán bằng lazy của nút cha.
        lazy[ch][2 * id] = lazy[ch][id]; 
        lazy[ch][2 * id + 1] = lazy[ch][id];
    }
	
    lazy[ch][id] = -1;
}

void update(int id, int u, int v, int l, int r, int val, int ch) 
{
    lazy_update(id, u, v, ch);
	
    if (u > r || v < l) 
        return;
	
    if (u >= l && v <= r) 
    {
        lazy[ch][id] = val;
        lazy_update(id, l, r, ch);
		
        return;
    }
	
    int mid = (u + v) >> 1;
    update(2 * id, u, mid, l, r, val, ch);
    update(2 * id + 1, mid + 1, v, l, r, val, ch);
	
    st[ch][id] = st[ch][2 * id] + st[ch][2 * id + 1];
}

int get(int id, int u, int v, int l, int r, int ch) 
{
    lazy_update(id, u, v, ch);
	
    if (u > r || v < l) 
        return 0;
	
    if (u >= l && v <= r) 
        return st[ch][id];

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

int main() 
{
    int n, q;
    cin >> n >> q;
	
    string s;
    cin >> s;
    s = ' ' + s;
    
	build_tree(1, 1, n, s);

    while (q--) 
    {
        int i, j, k;
        cin >> i >> j >> k;

        for (int ch = 0; ch <= 25; ++ch) 
        {
            cnt[ch] = get(1, 1, n, i, j, ch);
            update(1, 1, n, i, j, 0, ch);
        }

        int ch = (k ? 0 : 25), l = i;
        while (0 <= ch && ch <= 25) 
        {
            if (cnt[ch]) 
            {
                update(1, 1, n, l, l + cnt[ch] - 1, 1, ch);
                l += cnt[ch];
            }
			
            ch += (k ? 1 : -1);
        }
    }

    // In ra đáp án
    for (int i = 1; i <= n; ++i)
        for (int ch = 0; ch <= 25; ++ch)
            if (get(1, 1, n, i, i, ch)) 
            {
                cout << (char) (ch + 'a');
                break;
            }
}

2. Búp bê Nga

Đề bài

Búp bê Nga hay Búp bê Matryoshka (Búp bê lồng nhau, Búp bê làm tổ, ...) là một loại búp bê đặc trưng của Nga. Thật ra đó là một bộ gồm những búp bê rỗng ruột có kích thước từ lớn đến nhỏ. Con búp bê nhỏ nhất sẽ được chứa đựng trong lòng con búp bê lớn hơn nó một chút, đến lượt mình con búp bê lớn được chứa trong một con búp bê khác lớn hơn, và cứ thế cho đến con lớn nhất sẽ chứa tất cả những con búp bê còn lại trong bộ.

Hùng có một bộ sưu tập búp bê Nga gồm $n$ con, con thứ $i$ có kích thước là $a_i \ (1≤i≤n)$ . Số búp bê được xếp lên bàn thành một hàng ngang với thứ tự lộn xộn về kích thước. Sau đó, Hùng yêu cầu những người bạn của anh ta tạo ra khoảng trống ở phía bên trái hàng ngang bằng cách lấy một con búp bê có kích thước nhỏ hơn ở bên tay trái, đặt vào một con búp bê có kích thước lớn hơn ở bên tay phải, và mỗi con búp bê lớn chỉ được phép chứa duy nhất một con búp bê nhỏ hơn ở bên trong nó. Nói cách khác, những người bạn của Hùng chỉ được phép sử dụng $3$ thao tác: Lấy một con búp bê ở bên trái lên $→$ Di chuyển nó sang phải $→$ Đặt nó vào một con búp bê lớn hơn.

Yêu cầu: Hãy xác định giá trị $k$ lớn nhất $\big(1≤k≤\left\lfloor{\frac{n}{2}}\right\rfloor\big),$ sao cho $k$ con búp bê bên trái nhất có thể đặt vào bên trong $k$ con búp bê liền kề bên phải, mỗi con búp bê lớn chỉ chứa duy nhất một con búp bê nhỏ. Lưu ý, con búp bê ở vị trí $i$ chỉ có thể đặt vào con búp bê ở vị trí $j$ nếu như $i<j$ .

Input:

Dòng đầu tiên chứa số nguyên dương $n,m$ – số lượng búp bê của Hùng và kích thước giới hạn của nó.
Dòng thứ hai chứa $n$ số nguyên dương $a_1,a_2,…,a_n \ (1≤a_i≤m)$ – kích thước $N$ con búp bê.

Ràng buộc:

$1 \le n, m \le 10^5$ .

Output:

Đưa ra giá trị $k$ lớn nhất thỏa mãn yêu cầu của đề bài.

Sample Input:

10 5
2 1 4 2 3 2 4 5 2 3

Sample Output:

Giải thích:

Ta có thể đặt $4$ con búp bê bên trái vào trong $4$ con búp bê bên cạnh theo thứ tự như sau: $1$ đặt vào $5, 2$ đặt vào $6, 3$ đặt vào $8, 4$ đặt vào $7$ .

Ý tưởng

Đặt \text{cnt_left}[i] là số lượng búp bê có kích thước $i$ ở $k$ con búp bê bên trái, \text{cnt_right}[i] là số lượng búp bê có kích thước $i$ ở $k$ con búp bê bên phải. Ban đầu ta khởi tạo hai mảng trên với $K = \left\lfloor{\frac{n}{2}}\right\rfloor$ .

Với một con kích thước $i$ bên trái, cần một con có kích thước tối thiểu là $(i + 1)$ ở bên phải. Đặt $d[i]$ là tổng độ chênh lệch giữa số lượng con búp bê kích thước $i$ bên trái và số lượng con búp bê kích thước lớn hơn $i$ ở bên phải, với $i = [m...1]$ . Vậy ta có công thức:

d[m] = -\text{cnt_left}[m] (\text{vì cnt_right}[m + 1] = 0) d[i] = d[i + 1] + \text{cnt_right}[i + 1] - \text{cnt_left}[i], \forall i: m - 1 \ge i \ge 1

Sau khi xây dựng xong các mảng nói trên, ta tiếp tục thuật toán như sau:

Xét $k$ giảm dần từ $\left\lfloor{\frac{n}{2}}\right\rfloor$ về $1,$ mỗi khi $k$ giảm đi $1$ vị trí, ta có:

\text{cnt_left}[a_k] giảm đi $1$ .
\text{cnt_right}[a_k] tăng thêm $1$ .
\text{cnt_right}[a_{2k}] giảm đi $1$ .
\text{cnt_right}[a_{2k - 1}] giảm đi $1$ .

Từ đây ta có giải thuật trâu $O(n^2)$ : Với mỗi giá trị $k,$ xây dựng lại các mảng \text{cnt_left}, \text{cnt_right} và $d$ tương ứng. Sau đó, để $k$ con búp bê bên trái thỏa mãn nhét dc vào $k$ con búp bê bên phải thì mọi giá trị $d[i]$ phải không âm (với mọi $i$ từ $1$ tới $m$ ), ta chỉ cần duyệt kiểm tra toàn bộ mảng $d$ và đưa ra kết quả $k$ lớn nhất tương ứng.

Nhưng ta cần cải tiến thuật toán này để pass toàn bộ test cases. Nhận thấy:

d[i] = \text{cnt_right}[m] + \text{cnt_right}[m - 1] + \cdots + \text{cnt_right}[i + 1] - \text{cnt_left}[m] - \text{cnt_left}[m - 1] - \cdots - \text{cnt_left}[i + 1] - \text{cnt_left}[i]

Điều này có nghĩa là:

Một thao tác tăng/giảm phần tử \text{cnt_right}[i] một đơn vị sẽ tương ứng với tăng/giảm đoạn $d[1...i - 1]$ một đơn vị.
Một thao tác tăng/giảm phần tử \text{cnt_left}[i] một đơn vị sẽ tương ứng với giảm/tăng đoạn $d[1...i]$ một đơn vị (lưu ý ở trường hợp cập nhật \text{cnt_left}[i] thì mảng $d$ sẽ cập nhật ngược lại do giá trị \text{cnt_left}[i] mang dấu âm trong công thức tạo ra mảng $d$ ).

Từ các nhận xét trên, ta xây dựng một Interval Tree kiểm soát mảng $d$ để thực hiện hai thao tác:

Cập nhật tăng/giảm đoạn $(u, v)$ .
Lấy giá trị nhỏ nhất của đoạn $d[1...m]$ .
Việc cập nhật sử dụng kĩ thuật Lazy Propagation sẽ giúp cho thao tác cập nhật giảm độ phức tạp xuống còn $O\big(\log_2 m \big)$ và có thể lấy full điểm bài toán.

Cài đặt

#include <bits/stdc++.h>
#define int long long
#define inf 1e9 + 7
#define task "Rusdoll."

using namespace std;

const int maxn = 1e5 + 10;
int n, m, a[maxn], cnt_left[maxn], cnt_right[maxn], d[maxn];
pair < int, int > st[4 * maxn];

void enter()
{
    cin >> n >> m;

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

// Lazy Update trên cây IT để giảm độ phức tạp về O(logm).
void lazy_update(int id) 
{
    int val = st[id].second;

    st[id * 2].first += val;
    st[id * 2].second += val;
    st[id * 2 + 1].first += val;
    st[id * 2 + 1].second += val;

    st[id].second = 0;
}

// Update cây IT tương ứng với update mảng cnt_left và cnt_right.
void update(int id, int l, int r, int u, int v, int val) 
{
    if (u > r || v < l)
        return;

    if (l >= u && r <= v)
    {
        st[id].first += val;
        st[id].second += val;
        return;
    }

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

    st[id].first = min(st[id * 2].first, st[id * 2 + 1].first);
}

void create_data()
{
    int mid = n / 2;

    for (int i = 1; i <= mid; ++i)
        ++cnt_left[a[i]];
    for (int i = mid + 1; i <= 2 * mid; ++i)
        ++cnt_right[a[i]];

    for (int i = m; i >= 1; --i)
    {
        d[i] = (i == m) ? -cnt_left[m] : d[i + 1] + cnt_right[i + 1] - cnt_left[i];
        update(1, 1, m, i, i, d[i]);
    }
}

void solution()
{
    for (int k = n / 2; k >= 1; --k)
    {
        // Lấy giá trị nhỏ nhất của mảng d[1...m].
        int mind = st[1].first; 

        if (mind >= 0)
        {
            cout << k;
            return;
        }

        // Update trực tiếp trên cây IT lưu dữ liệu mảng d.
        //  tương ứng với việc thay đổi mảng cnt_left và cnt_right.
        update(1, 1, m, 1, a[k], 1);
        update(1, 1, m, 1, a[k] - 1, 1);
        update(1, 1, m, 1, a[2 * k] - 1, -1);
        update(1, 1, m, 1, a[2 * k - 1] - 1, -1);
    }

    cout << -1;
}

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

    enter();
    create_data();
    solution();

    return 0;
}

Cây phân đoạn (phần 3) - Lazy Propagation

I. Đặt vấn đề

II. Kĩ thuật Cập nhật lười (Lazy Propagation)

Ý tưởng chung

Áp dụng vào bài toán

Cài đặt

Đánh giá

III. Bài toán minh họa

1. A simple task (Codeforces Round 312 Div. 2)

Đề bài

Ý tưởng

Cài đặt

2. Búp bê Nga

Đề bài

Ý tưởng

Cài đặt

IV. Bài tập áp dụng

V. Tài liệu tham khảo

Mục lục