公式解説の内容を前提とします。「バケット」を用いることで高速化しようという大枠については同様です。

簡単な高速化

公式解説の \(O(QB \log N)\) の \(\log N\) は「ある種類 \(t\) の前処理②の範囲内にある個数」を求めるための二分探索に対するものです。しかし、この範囲内の出現個数については、前処理②の段階で同時に計算することができます。

ですが、すべての区間 \(O(N^2/B^2)\) すべての \(t\) についてこれを管理しておくと、空間が \(O(N^2)\) となって余裕で死んでしまいます。

そこで、平面走査をして \(i\) を固定し、 \(j\) をふやしながら、\([i \times b, j \times b)\) を「前処理②の区間」としてもつクエリを処理していくことで、それぞれのクエリを \(\log N\) をつけずにこたえることができます。

公式解説にこの言及が存在しないのは、「多くの実装において連想配列を用いることとなり、結果としてあまり高速化が見込めないから」の可能性が高いですが、適切に座圧をして種類ごとに番号付けを（ \(A\) のすべての要素に対しても）してあげることで、ふつうの配列のみですべてを管理することは可能です。

これで、\(O(N \log N + N^2/B + QB )\) が達成可能です。（空間に関しても \(O(N)\) になります。）

少し変わった解法

ところで、このような一点更新はうまくいかないが、差分更新は可能な \(\text{static}\) な配列に対するクエリ問題は \(\text{Mo's algorithm}\) が強力であることがしられています。

今回のクエリで必要なのは、区間を動かすたびに 「一点更新」をし、クエリのときに「全体の \(\max \) 」を取れるような構造体です。一般的にこれは Segment tree を用いることで実装できることが知られています。これで、　\(O((N \sqrt Q +Q) \log N)\) を達成することができます。

ところで、（ネタバレになるため下に隠しておきますが）ある問題で提案されているように、「一点更新」を \(O(1)\)、「全体 \(\max\) 」を \(O(\sqrt N)\) ですることができれば、オーダーが、\(O(N \log N + N \sqrt Q + Q \sqrt N)\) となり、\(N \simeq Q\) の制約下では真に計算量が改善します。

実際に、この問題の制約下ではそのようなことが可能です。（要求するのは、「出現する値の候補が \(O(N)\) であること」です。これが \(O(N \sqrt N)\) の場合に同様な改善が存在するかはわかりませんでした）

・出現する値をすべて先読みして座圧を行う。
・「 \(\max\) をとる集合に現在含まれる要素」の頻度列を管理する。
・\(val\) が追加（削除）される時 \(cnt[val] \gets cnt[val] +1 (-1)\)
・\(\max\) は \(\text{sum}(cnt[0, x]) = \text{sum}(cnt)\) となる最小の \(x\) であり、これは（Segment tree上の）二分探索でもとまる。

上記のようにすることで、Segment treeで解くことができます。しかし、頻度列に対して平方分割をすることで、所望の計算量で解くこともできます。よって改善されました。