JOI2014 春合宿 - 歴史の研究

• 問題
• AC

オフラインなのでMo's algorithmが適用できる。つまり、平衡二分木（あるいはセグメント木+座標圧縮）などを用意して、区間$[l, r]$を$[l, r+1]$に伸ばすときは$dp[X_{r+1}] += X_{r+1}$と更新して、$[l, r]$を$[l, r-1]$に縮めるときは$dp[X_r] -= X_r$とすればよい。$[l, r]$から$[l-1, r]$、$[l, r]$から$[l+1, r]$なども同様である。それぞれのクエリについて$\max dp$が答えになっている。${O}(N \sqrt{Q} \log N)$。

---

平衡二分木を使ったらTLEしてしばらく放置していたが、よく考えると全体の$\max$にしか興味がないので（優先度の変更可能な）優先度付きキューを使えば十分なのを思い出した。えびちゃんさんの記事にやり方が載っているので、書いたら通った。