Editorial for Hàm số và truy vấn

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: Yunan

Subtask 1: Với điều kiện đã cho, ta cần tính các giá trị $\mathrm{F}(x)$ ~\mathrm{F}(x)~ với $1 \le x \le 4002000$ ~1 \le x \le 4002000~. Với mỗi truy vấn, ta đơn giản tính tổng các giá trị $\mathrm{F}(A_i)$ ~\mathrm{F}(A_i)~.

Độ phức tạp: $O(Q.N)$ ~O(Q.N)~

Subtask 2: Dễ dàng nhận thấy dãy số $\mathrm{F}$ ~\mathrm{F}~ chính là dãy $\mathrm{Fibonacci}$ ~\mathrm{Fibonacci}~. Có thể tính toán giá trị số $\mathrm{Fibonacci}$ ~\mathrm{Fibonacci}~ thứ $x$ ~x~ trong $O(log(x))$ ~O(log(x))~ bằng phương pháp Nhân ma trận.

Độ phức tạp: $O(Q.N.log(c))$ ~O(Q.N.log(c))~

Subtask 3: Ta chỉ cần thực hiện các truy vấn loại $2$ ~2~ thông qua việc xây dựng mảng cộng dồn đối với các giá trị $\mathrm{F}(A_i)$ ~\mathrm{F}(A_i)~.

Độ phức tạp: $O(N.log(c)+Q)$ ~O(N.log(c)+Q)~

Subtask 4: Sử dụng cấu trúc Segment Tree và kỹ thuật Lan truyền lười nhác $($ ~(~Lazy Propagation $)$ ~)~ để giải quyết bài toán. Nút lá thứ $i$ ~i~ là ma trận biểu diễn số $\mathrm{Fibonacci}$ ~\mathrm{Fibonacci}~ thứ $i$ ~i~ và mỗi nút của cây là tổng ma trận của các nút con.

Độ phức tạp: $O((N+Q).log(N).log(c))$ ~O((N+Q).log(N).log(c))~

Editorial for Hàm số và truy vấn

Comments