Có 1 dãy số và 1 danh sách các thao tác trên dãy số đó.Dãy số lúc đầu k chứa phần tử nào , có 2 loại thao tác
'+ x': thêm 1 phần tử giá trị x vào dãy
'- x':xóa đi 1 phần tử giá trị x trong dãy
Nhiệm vụ tính UCLN của dãy sau mỗi thao tác
(Dữ liệu đảm bảo rằng tháo tác xóa chỉ có những phần tử đang có trong dãy)
input: dòng đầu chứa Q(số lượng thao tác) Q<=10^5, Q+1 dòng tiếp theo chứa các thao tác
output:Gồm Q dòng biểu dễn UCLN
input ouput
5
+8 8
+6 2
+8 2
-8 2
-8 6
Tạo một cây nhị phân chứa giá trị các phần tử và thêm một trường chứa UCLN của tất cả các phần tử trên cây con có gốc là nút đấy. Sau khi chèn hay xóa ta cập nhập lại trường đấy. Giá trị xuất ra sau mỗi thao tác là giá trị trường chứa UCLN của nút gốc.
anh trả lời rõ hơn được k ạ?
Mình thấy cách của bạn bvd là khả thi, không hiểu sao lại bị vote trừ :v
Có thể cài đặt offline đơn giản hơn mà không cần đến BBST: sort các giá trị xuất hiện trong input lại rồi dựng cây IT trên mảng chứa các giá trị khác nhau tăng dần. Mỗi node IT lưu GCD của đoạn và nếu là node lá thì lưu thêm số lượng giá trị tương ứng. Với mỗi truy vấn tìm kiếm nhị phân để tìm ra vị trí rồi cập nhật trên IT như bình thường. ĐPT cỡ O(Q * logN * logMAXV).
Nếu chặn trên của các số trong input là nhỏ (cỡ 10^6) thì có thể giải cách khác bằng cách phân tích thừa số nguyên tố.
Dựng cây IT lưu GCD các đoạn với node là các truy vấn.
Với truy vấn i là '+ x': update cho node thứ i giá trị x. kq=GCD(kq, x).
Với truy vấn i là '- x': tìm vị trị j là truy vấn '+ x' gần nhất. kq=GCD(GCD[1>>j-1], GCD[j+1>>i-1]). Sau đó xóa giá trị ở node j.
