まずは公式解説をお読みください。

平方分割をすることでもこの問題を解くことが出来ます。

公式解説で \([0,T+1),\ [0,\lfloor \frac{T-1}{2} \rfloor), \ \dots\) の順に再帰的に求めているところを、\([0,D)\ [0,2\times D), \dots\) (\(D\) はバケットサイズ) の順に求めていけば良いです。

解答例：https://atcoder.jp/contests/abc213/submissions/24889465 (AC Library, \(D=\lfloor 4\sqrt{T}\rfloor\), 4276ms)