Trong bài toán này, chúng ta được cho một số N là kích thước mảng toàn số 0 và Q truy vấn mỗi loại sau −
update(s, e, val) -> truy vấn này sẽ cập nhật tất cả phần tử từ s đến e (tính cả hai đầu) thành val.
Nhiệm vụ của chúng ta là tìm số lượng số khác nhau trong mảng sau khi áp dụng thao tác q lần
Hãy xem ví dụ sau để hiểu bài toán:
Input : N = 6, Q = 2 Q1 = update(1, 4, 3) Q2 = update(0, 2, 4) Output : 2
Giải thích
Mảng ban đầu, arr[] = {0, 0, 0, 0, 0, 0}
Truy vấn 1 − update(1, 4, 3) -> arr[] = {0, 3, 3, 3, 3, 0}
Truy vấn 2 − update(0, 2, 4) -> arr[] = {4, 4, 4, 3, 3, 0}
Phương pháp giải
Một giải pháp đơn giản là thực hiện từng truy vấn trên mảng và đếm số giá trị duy nhất dùng mảng phụ. Sau đó trả về số lượng giá trị duy nhất.
Giải pháp này tốt nhưng giải pháp hiệu quả hơn là sử dụng khái niệm lazy propagation để tối ưu hóa thao tác phạm vi trong truy vấn. Ta sẽ dùng lazy propagation cho truy vấn để tìm số lượng số duy nhất. Với điều này ta dùng cây đoạn và cập nhật nút khi thực hiện thao tác và khởi tạo cây với giá trị 0, các giá trị cập nhật trả về kết quả mong muốn. Chương trình dưới đây sẽ giải thích rõ hơn.
Ví dụ
Chương trình minh họa cho giải pháp
#include <bits/stdc++.h> using namespace std; #define N 100005 int lazyST[4 * N]; set<int> diffNo; void update(int s, int e, int val, int idx, int l, int r){ if (s >= r or l >= e) return; if (s <= l && r <= e) { lazyST[idx] = val; return; } int mid = (l + r) / 2; if (lazyST[idx]) lazyST[2 * idx] = lazyST[2 * idx + 1] = lazyST[idx]; lazyST[idx] = 0; update(s, e, val, 2 * idx, l, mid); update(s, e, val, 2 * idx + 1, mid, r); } void query(int idx, int l, int r){ if (lazyST[idx]) { diffNo.insert(lazyST[idx]); return; } if (r - l < 2) return; int mid = (l + r) / 2; query(2 * idx, l, mid); query(2 * idx + 1, mid, r); } int main() { int n = 6, q = 3; update(1, 3, 5, 1, 0, n); update(4, 5, 1, 1, 0, n); update(0, 2, 9, 1, 0, n); query(1, 0, n); cout<<"The number of different numbers in the array after operation is "<<diffNo.size(); return 0; }Kết quả
The number of different numbers in the array after operation is 3