kmjp https://blog.hatena.ne.jp/kmjp/ kmjp's blog https://kmjp.hatenablog.jp/ Codeforces Div2とはいえ、Eになると実装が結構しんどい… それでは最終問題。 http://codeforces.com/contest/266/problem/E 数列に対してクエリが送られるので、数値を更新したり部分列から計算されるスコアを返す問題。 数列の要素数Nが最大100000個、クエリ数Qも100000個なので、O(NQ)よりも小さく処理しないとダメ。正式なEditorialよりも、blogのページ中のkraskevich氏のコメントの方がわかりやすかったので、これを見て実装。基本的には、セグメントツリーを作って数列の部分に対する和を計算しておき、クエリに対してそれらを取り出して返す。 ち… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkmjp.hatenablog.jp%2Fentry%2F2013%2F02%2F02%2F1030" title="Codeforces #163 Div2. E. More Queries to Array... - kmjp&#39;s blog" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2013-02-02 10:30:00 rich https://kmjp.hatenablog.jp/entry/2013/02/02/1030 1.0 100%