CF1634F Fibonacci Additions
mango09
·
·
题解
F. Fibonacci Additions
维护 A 和 B 的差数组 D，D_i = 0 意味着 A_i = B_i，所以问题转化为求 D 中是否全为 0。
动态统计 D 中元素 0 的个数。用线段树是不好统计的，我们可以使用差分。
根据斐波那契数列的特点 f_n = f_{n - 1} + f_{n - 2}，令差分数组 c_n = D_n - D_{n - 1} - D_{n - 2}，这样在对 D 区间加或减斐波那契数列时，只有 c_l, c_{r + 1}, c_{r + 2} 会发生变化，变化量也是非常好算的，不在正文中赘述。
观察到只有当 c 中全为 0 时，D 中才能全为 0，于是只需要暴力维护 c 中 0 的个数 cnt，询问时判断 cnt 是否等于 n 即可。
Code