xyd noip round t3 求问

[stringdp100005]

会 O(q\log^2 n) 没打完，题解里的 O(q\log n) 的做法没看懂。O(q\log^2 n) 的做法是否为正解，单 log 是怎么做的。