Official

L - マンションの改築 Editorial by camypaper


操作 \(1,2\) で愚直にマンションの高さを変更すると \(O(NQ)\) となってしまいます。 まずはこの操作を言い換えることを考えます。

整数 \(X\) を用意しておきます。はじめ \(X=0\) です。 操作 \(1\)\(X\)\(X+v\) に、操作 \(2\)\(X\)\(X-v\) に置き換えるという操作に言い換えておきます。

すると、隣り合うマンションの高さが等しいものを数えるのではなく、隣り合うマンションの組のうち奇数番目のマンションが \(X\) だけ高いようなものの個数を数えればよいことになります。

隣り合うマンションの高さの差は操作 \(3\) によってのみ変化しますが、変化する箇所は高々 \(2\) 箇所です。 マンションの高さの差と、その出現頻度を連想配列によって管理することで \(O(\log N)\) で更新可能です。 全体として、\(O(N+Q \log N)\) で実行可能で十分高速です。

posted:
last update: