取得:最大値・最小値
NoviSteps2Q
鉄則本
鉄則本A問題
鉄則本★4
AtCoder
累積和テク:左右両端からの累積和や累積結果を前処理
前処理
累積和
累積max
クエリ処理問題
N個のものうち1個を変更・削除したものを解く
取得:区間
取得:最大値・最小値
そのまま覚えたい典型問題
左右からの累積和・累積 max を前処理で求めておくのは、よくある典型!! 問題へのリンク 問題概要 個の整数からなる数列 が与えられる。次の 個のクエリに答えよ。 【クエリ】 区間 が与えられるので、数列からその区間を除外した領域について、整数値の最…
AtCoder
AtCoder475点
ABC-E
緑色diff
setの上手な使い方
連想配列(setやmap)
遅延評価セグメント木
セグメント木上の二分探索
mex
補集合を考える
見積り大事
テク:区間をsetで管理する
数列
クエリ処理問題
操作:値の更新
削除可能priority_queue
操作:削除
取得:最大値・最小値
データ構造をいい感じに設計する地力が問われる! 問題へのリンク 問題概要 長さ の数列 が与えられる。この数列に対する以下の 個のクエリに答えよ。 各クエリでは整数 が与えられる を に置き換える 置き換えたあとの数列 の mex を出力せよ 制約 考えたこ…
AtCoder
鉄則本A問題
そのまま覚えたい典型問題
セグメント木
クエリ処理問題
データ構造
RMQ
【問題集】セグメント木の入門
数列
鉄則本
NoviSteps1Q
鉄則本★5
取得:最大値・最小値
取得:区間
セグメント木の最初の練習問題によさそうな問題 問題へのリンク 問題概要 長さ の数列 がある。最初はすべての要素が 0 となっている。この数列に対して、以下の 2 種類のクエリに答えよ ( 個のクエリが与えられる)。 クエリ 1: が与えられるので、 の値を …