【题解】CF1968G2 Division + LCP

· · 题解

这是 G1 的题解。

考虑怎么将这个问题推广到 G2。如果对于 i\in [l,r] 每个都做一次二分，显然太浪费了。

类比整体二分的思路，我们记 solve(l,r,q_l,q_r) 为 [q_l, q_r] 的询问的答案在 [l,r] 内。

我们记 mid=\left\lfloor\dfrac{l+r}{2}\right\rfloor，然后将 [q_l,q_r] 分成两部分，递归 solve(l,mid,ql,qmid) 和 solve(mid+1,r,qmid+1,qr) 即可。

根据 LA 群的分析，时间复杂度 \Theta(n\sqrt n)。

Submission for G2.