けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

【問題集】セグメント木の入門

AtCoder Library Practice Contest J - Segment Tree

セグメント木の練習問題です。 クエリタイプ 1, 2 のみなら、ただの RMQ ですね。クエリタイプ 3 は、セグメント木上の二分探索を実行する関数 max_right() が使えます。 問題へのリンク 問題概要 長さ の数列 がある。この数列に対して、以下の 2 種類のク…

鉄則本 A58 - RMQ (Range Maximum Queries)

セグメント木の最初の練習問題によさそうな問題 問題へのリンク 問題概要 長さ の数列 がある。最初はすべての要素が 0 となっている。この数列に対して、以下の 2 種類のクエリに答えよ ( 個のクエリが与えられる)。 クエリ 1: が与えられるので、 の値を …

AtCoder Library Practice Contest B - Fenwick Tree

BIT の使い方の練習問題。同時に、自分で BIT を書いたときにそれを verify できる問題でもある! 問題へのリンク 問題概要 長さ の数列 が与えられる。この数列に対する 個のクエリに答えよ。 :数列中の値 に を加算する (a[p] += x) :数列 の区間 の総和…

AtCoder ABC 185 F - Range Xor Query (緑色, 600 点)

ABC-F が緑色 diff になったのは史上初かな!?!??? でもセグ木が緑色はびっくり!!! 問題へのリンク 問題概要 長さ の非負整数列 がある。これに対して以下の 個のクエリに答えよ。 タイプ 1:整数 が与えられる。 を XOR で置き換えよ。 タイプ 2:…

AtCoder ABC 170 E - Smart Infants (水色, 500 点)

こういうの苦手すぎるので、素早く綺麗に実装できるようになりたい 問題へのリンク 問題概要 AtCoder に参加している幼児が 人おり、 から の番号が付けられている。また、幼稚園 がある。幼児 のレートは であり、はじめ幼稚園 に所属している。 これから …