考虑进一步优化，我们发现对于后三种转移，若确定了 i 或 j 中 v 有被钦定值的一个（若都是 -1 则随便一个），随着另一个的远离，只会在区间上交上更多的区间，所以 T 的值是单调的。所以可以二分出可以转移到的区间，或可以向它转移的区间，使用线段树优化 dp 转移，这个可以做到 O(n\log n)。但第一种转移比较困难，原因是转移点并不单调，也不是一段区间，所以看起来比较难办。
不过我们可以根据这个 dp 的含义发现对于一个 i，只需要从最后一个能转移的 j 向 i 转移即可。这是为什么呢？因为当 i 固定时，b_{2i} 被固定了，所以前面所有的 b 其实都已经被确定。这样如果有两个转移点 l<r，不管使用哪种转移，b_{2r-1} 总是等于 b_{2r}。而我们在 f_l\to f_i 的时候没有考虑这一个贡献，相反，若我们先从 f_l\to f_r，再从 f_r\to f_i，这一定合法，并且会计算这个贡献，因此一定更优。这样一来，我们只需要能够找到最后一个转移点即可。而从 j\to i 的转移，除了需要满足 j 在前面求出的 i 的可被转移到的区间中以外，还需要满足的条件是一个关于 a_i,a_j,s_i,s_j（s 是预处理的前缀和），以及 i,j 的奇偶性的线性方程。所以分 i,j 的奇偶性，将方程移项之后把关于 j 的项的值存入 map，查询关于 i 的项的值在对应 map 中的最大位置并判定是否合法即可。所以复杂度 O(n\log n)，总复杂度 O(n\log n)。