drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ クエリ処理問題 セグメント木 データ構造テク：全体に反映させる値を別にもつ(遅延評価) 平方分割 クエリ(木上) 木 Eulerツアー AOJ RUPC 遅延評価セグメント木 NoviSteps3D オイラーツアー第三弾！ RUPC 2018 で見たばかりの問題でもある。 問題へのリンク 問題概要 頂点 1 を根とする頂点数 N の根付き木が与えられる。初期状態で各頂点に G または W の属性が割り振られている。以下の Q 個のクエリに答えよ: v: 頂点 v を根とする部分木の「G」と「W」を入れ替えたのち、「G」を「W」のうちのどちらがより多くなっているかを判定せよ 制約 1 <= N, Q <= 105 考えたこと 根付き木の部分木に関する問題だからいかにもオイラーツアーっぽい。オイラーツアー上では、「部分木に対する操作」は「区間に対する操作」に対応するし、「部分木に関する値」は「… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2018%2F08%2F07%2F232300" title="AOJ 2871 ブロッコリー？カリフラワー？ (RUPC 2018 day3-E) (3D) - けんちょんの競プロ精進記録" 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 2018-08-07 23:23:00 rich https://drken1215.hatenablog.com/entry/2018/08/07/232300 1.0 100%