A Most Popular Matcha’s Snow Land (Easy)

この問題は主に一次元imos法を問います。

Easy の解説です。
配列を用いて質問毎に毎回答えるシミュレーションをしていくと、最悪 $O(N^2+NQ)$ で時間制限に間に合いません。
そこで各質問を $O(1)$ で事前に処理し、後々に累積和を用いたアルゴリズム( imos法 )を用いて実装してみます。この問題では各日にちにおいての予約数を要素とする配列 $D$ を定義し、これを用いて以下のように事前に処理し、累積和を用いることでそれぞれの日の予約数を合計 $O(N)$ で求めることができます。

• $L_i$ 日目から $R_i$ 日目のそれぞれに予約が $1$ つずつ入る、すなわち区間 $[L_i,R_i)$ において $D_{L_i},D_{L_i+1},...D_{R_i}$ に $1$ ずつ足していく時、$D_{L_i}$ から足していくので $D_{L_i}=1$ とし、$D_{R_i+1}$ からは予約が $1$ つ少なくなるため $D_{R_i+1}=-1$ を格納する

また最後に予約数の最大値の導出とそのカウントですが、制約上最悪 $O(NQ)$ が間に合うので愚直に探索し、愚直にカウントすればよいです。よって最初に入力する部分を含め $O(M+NQ)$ この問題を解くことができます。

以下は解答例(C++)です。