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

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

セグメント木

JOIG 春合宿 2023 day2-2 White Light (難易度 8)

セグメント木を用いた DP 高速化! 問題へのリンク editorials 問題概要 'R' と 'G' と 'B' のみからなる長さ の文字列 が与えられる。以下の操作を繰り返し行うことで、"RGB" を繰り返す文字列となるようにしたい。 (操作) 連続する 個以下の文字を消す 目…

AtCoder ARC 167 D - Good Permutation (黄色, 700 点)

モノグサでバチャやって、なんとか通した! 問題へのリンク 問題概要 の順列 が与えられる。この順列に対して「2 個の要素を選んで swap する」という操作を実行して、 「順列から誘導される Functional Graph の連結成分の個数が 1 個」 という状態を実現し…

AtCoder Library Practice Contest L - Lazy Segment Tree

タイトル "Lazy Segment Tree" の名の通り、遅延評価セグメント木の練習問題! 問題へのリンク 問題概要 長さ の 0 と 1 のみからなる数列 が与えられる。この数列に対して、次の 回のクエリに答えよ。 クエリタイプ 1 ():数列の区間 内の各要素の値につい…

Yosupo Library Checker - Range Affine Range Sum

これ実は ACL Practice Contest の K 問題と同じらしい atcoder.jp 問題へのリンク 問題概要 長さ の数列 が与えられる。この数列に対して、次の 回のクエリに答えよ。 クエリタイプ 1 ():数列の区間 内の各要素の値を 倍して を足せ クエリタイプ 2 ():数…

AtCoder Library Practice Contest K - Range Affine Range Sum

遅延評価セグメント木の練習! 問題へのリンク 問題概要 長さ の数列 が与えられる。この数列に対して、次の 回のクエリに答えよ。 クエリタイプ 1 ():数列の区間 内の各要素の値を 倍して を足せ クエリタイプ 2 ():数列の区間 内の要素の総和を 99824435…

AtCoder Library Practice Contest J - Segment Tree

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

AtCoder ABC 327 F - Apples (青色, 550 点)

遅延セグ木 (区間加算 + 区間 max 取得) を用いた平面走査! 問題へのリンク 問題概要 二次元平面上に 個の点がある。点 の座標は である。 この 2 次元平面上でサイズが の長方形領域 (右辺と上辺は含まない) を自由に動かしていくとき、この長方形領域に覆…

AtCoder ABC 322 F - Vacation Query (青色, 550 点)

遅延評価セグメント木の練習問題! 問題へのリンク 問題概要 0 と 1 のみからなる長さ の文字列 が与えられる。次の 2 種類のクエリに答えよ。 クエリ (1 L R):文字列 の区間 内における、1 が連続する区間の長さの最大値を答えよ クエリ (2 L R):文字列 …

AOJ Course RSQ and RUQ (遅延評価セグメント木の練習問題 4)

「区間値更新」と「区間和取得」の遅延評価セグ木。 問題へのリンク 問題概要 数列 に対して、次の 2 種類のクエリを 個処理せよ。なお、数列は最初は 0 に初期化されているとする。 クエリタイプ (0 s t x): を に変更する クエリタイプ (1 s t): の総和…

AOJ Course RSQ and RAQ (遅延評価セグメント木の練習問題 3)

「区間加算」と「区間和取得」の遅延評価セグ木。 問題へのリンク 問題概要 数列 に対して、次の 2 種類のクエリを 個処理せよ。なお、数列は最初は 0 に初期化されているとする。 クエリタイプ (0 s t x): に を加算する クエリタイプ (1 s t): の総和を…

AOJ Course RMQ and RUQ (遅延評価セグメント木の練習問題 2)

Starry Sky Tree は「区間 加算」「区間最小値取得」を処理する遅延セグ木だった。 今回は「区間 更新」「区間最小値取得」を処理する遅延セグ木を実装する。 問題へのリンク 問題概要 数列 に対して、次の 2 種類のクエリを 個処理せよ。なお、数列は最初は…

AOJ Course RMQ and RAQ (遅延評価セグメント木の練習問題 1)

この問題は、人生で最初に挑む遅延セグ木の問題としてオススメ!Starry Sky Tree と呼ばれるものでもある。 問題へのリンク 問題概要 数列 に対して、次の 2 種類のクエリを 個処理せよ。なお、数列は最初は 0 に初期化されているとする。 クエリタイプ (0 s…

鉄則本 A58 - RMQ (Range Maximum Queries)

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

ウクーニャたんお誕生日コンテスト D - ukuku

ネタコンテストなのかと思いきや、問題面白くて、この D 問題は勉強になった。答え決め打ちの二分探索! 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。 この文字列について 回のクエリに答えたい。 各クエリでは整数値 が与えられ…

AtCoder ABC 307 F - Virus 2 (黄色, 550 点)

セグ木上二分探索使ったというコメントをよく見たけど、僕の方針でも使うことになった 問題へのリンク 問題概要 頂点数 、辺数 の単純な重み付き無向グラフが与えられる。 日目、 個の頂点 がウィルスに感染した。一度ウィルスに感染した頂点はずっと感染し…

AtCoder ABC 278 D - All Assign Point Add (茶色, 400 点)

データの持ち方をうまく工夫することで、計算量を改善する系の問題! 問題へのリンク 問題概要 長さ の数列 が与えられる。 個のクエリが与えられるので、それらを順に処理せよ。クエリは次の 3 種類ある。 x:数列 をすべて に書き換える i x: に を足す i…

AtCoder ABC 280 Ex - Substring Sort (銅色, 600 点)

Suffix Tree 上で DFS した。デバッグがめっちゃ大変だった! 問題へのリンク 問題概要 個の英小文字からなる文字列 が与えられる。 これら 個の文字列について、連続する部分文字列をすべて考える。重複を除かずに考えると 個ある。 これら 個の文字列を辞…

AOJ 2644 Longest Match (JAG 夏合宿 2014 day4-F) (700 点)

Suffix Array の練習問題 問題へのリンク editorials へのリンク 問題概要 英小文字からなる文字列 と、 個のクエリが与えられる。 各クエリでは 2 つの文字列 が与えられる。 文字列 の連続する部分文字列であって、 で始まり、 で終わるものの中で、最長の…

AtCoder Library Practice Contest B - Fenwick Tree

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

AtCoder ABC 281 E - Least Elements (水色, 500 点)

よくあるデータ構造問題!! めっちゃ色んな解法がある! 問題へのリンク 問題概要 長さ の整数列 と整数 が与えられる (0-indexed で表している)。 各 に対して、次の問題に答えてください。 個の整数 を小さい順に並び替えたときの先頭 個の総和を求めよ。…

EDPC (Educational DP Contest) W - Intervals

まさに、「DP 配列をセグメント木に載せる」というセグ木上の in-place DP ですね!!! 問題へのリンク 問題概要 0 と 1 のみからなる長さ の文字列を 0-1 文字列と呼ぶことにします。 今、文字列中の 個の連続する区間 ( 番目の区間を とします) が与えら…

EDPC (Educational DP Contest) Q - Flowers

まさに重み付き LIS ともいうべき問題ですね。 問題へのリンク 問題概要 本の花が横一列に並んでいます。 左から 番目の花の高さは で、美しさは です。 太郎君は何本かの花を抜き去ることで、次の条件が成り立つようにしようとしています。 「残った花を左…

パ研合宿2020 第1日「SpeedRun」 N - 背の順

面白かった!セグ木を使ったけど、区間を複数個にする必要がないことから、しゃくとり法で線形でできるね! 問題へのリンク 問題概要 の順列 が与えられる。以下の操作を繰り返すことで、単調増加となるようにしたい。 区間 の要素をすべて削除する (コスト…

AtCoder AGC 050 A - AtCoder Jumper (500 点)

これ本当にずっとわからなかった...言われてみればという感じ!! 問題へのリンク 問題概要 以下の条件を満たす、頂点数 の有向グラフ (頂点番号を とする) を構築せよ (自己ループも多重辺も可)。 すべての頂点の出次数は 2 である 任意の頂点対 に対して、…

Codeforces Round #673 (Div. 1) D. Graph and Queries (R2600)

いろんな方法がありそう。Union-Find のマージ過程を表す木でやったけど、ほかにも Undo 付き Union-Find を使うなど 問題へのリンク 問題概要 頂点数 、辺数 のグラフが与えられる。初期状態では各頂点に という値がついている (すべて 1 以上で disjoint)…

AOJ 2880 エレベータ (RUPC 2018 day1-G)

昔はこういうの苦手だったけど、今ならできる! 問題へのリンク 問題概要 階建ての建物があって、後述するエレベータの建設をなくしては、下への移動は自由にできるが、上への移動は自由にできない。 個のエレベータ建設計画がある。 番目の計画では、 日目…

AtCoder ABC 186 F - Rook on Grid (青色, 600 点)

「横移動 + 縦移動」で行けるところをすべて求めるのは簡単だし、「縦移動 + 横移動」で行けるところをすべて求めるのも簡単。しかし、両方の方法で行けるマスの扱いが難しい。 問題へのリンク 問題概要 のグリッドがあり、そのうちの 個のマスは壁になって…

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

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

AtCoder ARC 108 E - Random IS (赤色, 700 点)

変なところでハマらないようにしたい... 問題へのリンク 問題概要 の順列 が与えられる。いま、これらの順列の各要素に印をつけていくことを考える。ただし、「印のついた要素が左から順に単調増加となるように並んでいる」という条件を常に満たす必要がある…

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

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