Editorial for Bedao Mini Contest 09 - SOR


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Trước hết ta nên nhận xét được một dãy sẽ thỏa khi nào.

Xét 2 bit ~a~ và ~b~, ta có bảng toán tử sau :

a b a + b a or b
0 0 0 0
0 1 1 1
1 0 1 1
1 1 2 1

Nhìn bảng, ta thấy được phép cộng và phép or chỉ có kết quả khác nhau khi ~a = b = 1~.

Vậy ta kết luận : Một dãy thỏa khi và chỉ khi, với mỗi vị trí bit, có nhiều nhất ~1~ bit ~1~ xuất hiện trong dãy.

Tuy nhiên nếu ta cứ chạy và cập nhật ngây thơ thì sẽ dễ dàng chạy quá thời gian, nên chúng ta sẽ có thêm nhận xét sau.

Nhận xét quan trọng : Vì ~a_i > 0~, nên ~a_i~ có ít nhất một bit ~1~.

Hệ quả : Dãy thỏa không bao giờ dài quá ~log_2(a_i)~.

Từ đó ta có thuật toán đơn giản sau :

  • Gọi ~ans_u~ là dãy thỏa dài nhất bắt đầu từ vị trí ~u~. Dễ thấy đáp án là ~max(ans_i)~. Ta sẽ dùng set hoặc heap (hoặc bất kỳ ctdl nào bạn muốn) để lưu lại các số trong mảng ~ans~ để tiện lấy đáp án.
  • Ban đầu precalculate mảng ans trong ~O(n * log(a_i))~.
  • Với truy vấn cập nhật ở vị trí ~u~, ta chỉ cập nhật lại ~ans_i~ với ~u - 31 \le i \le u~. Độ phức tạp : ~O(log^2(a_i))~ hoặc ~O(log(a_i))~ nếu dùng 2 con trỏ.
  • Vì sau mỗi truy vấn có tối đa ~log(a_i)~ giá trị ~ans_i~ được cập nhật lại nên ta sẽ cập nhật lại đáp án trong : ~O(log(n) \times log(a_i))~

Vậy độ phức tạp của thuật toán là : ~O(q \times log(a_i) \times (log(a_i) + log(n)))~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.