drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder600点 ABC-F 緑色diff データ構造 クエリ処理問題 BIT セグメント木 【問題集】セグメント木の入門 ABC-F が緑色 diff になったのは史上初かな！？！？？？ でもセグ木が緑色はびっくり！！！ 問題へのリンク 問題概要 長さ の非負整数列 がある。これに対して以下の 個のクエリに答えよ。 タイプ 1：整数 が与えられる。 を XOR で置き換えよ。 タイプ 2：整数 が与えられる。 XOR XOR ... XOR の値を出力せよ。 制約 解法 (1)：セグメント木を使う 今回のように、 配列の 1 点のみを更新する 配列の区間についての総和 (今回は XOR 和についての総和) を求める という処理を高速に実現できるデータ構造として、セグメント木がある。 ACL にはセグメント木がある… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F12%2F14%2F005700" title="AtCoder ABC 185 F - Range Xor Query (緑色, 600 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2020-12-14 00:57:00 rich https://drken1215.hatenablog.com/entry/2020/12/14/005700 1.0 100%