A Most Popular Matcha’s Snow Land (Hard)

この問題 (Hard) は主に高度なデータ構造、連想配列、区間における添字の二分探索を問います。

Hardの解説です。
Easyでは最後の $Q$ 個の質問に答えるのに愚直に予約数の最大値とその個数を数えていましたが、Hardでは $Q\le 3\times 10^5$ から時間制限に間に合わないので、この部分を高速化させる必要があります。
Easyでimos法を図った配列 $D=(D_1,D_2,...D_{c})$ ( $c$ は配列 $D$ の長さ) において、各要素 (すなわち $D_i\ (1\le i\le c)$ )毎に添え字をとった配列 $T_{D_i}(=i_1,i_2,...i_n)$ ( $i_p\ (1\le p\le n)$ は $D_{i_p}=D_l$ となる添え字 $l$ 、また $n$ は $D_{i_p}=D_l$ となる $l$ の個数) とし、$T_{D_i}$ を"値"、$D_i$ を"キー"として持った連想配列 $P(=\{[D_1][T_{D_1}],[D_2][T_{D_2}],...[D_c][T_{D_c}]\})$ を用います。

このままでは $1\le i\le Q$ において、$L_j$ 日目から $R_j$ 日目までの区間において予約数の最大値を $K$ として、"キー"が $K$ に対応する $P$ の要素において $L_j$ 以上 $R_j$ 以下の要素の個数を愚直に探索することで求められますが、高速化を図ることはできません。しかし $T$ は単調増加性を持つ ( $k=1,2,...c$ からこの順に添え字を順番に格納していくため) ことから、二分探索を用いて条件を満たす要素の個数を高速に求めることができます※。

また $K$ はどうやって求めるのかというと、これはセグメントツリーや Sparse Table などの、ある区間に対する最大値/最小値を高速に求める高度なデータ構造を用いて求めることが可能です。以上を用いることで時間制限に間に合わせることができるような実装が可能です。

※この個数を求める部分問題に似た類題 ABC248-D がありますので、そちらも参考にしてください。