取得:個数
AtCoder
AtCoder350点
ABC-C
NoviSteps3Q
文字列
データ構造
クエリ処理問題
データ構造テク:差分更新
操作
操作:1文字を変更する
取得:個数
そのまま覚えたい典型問題
灰色diff
差分のみ更新していく系の典型問題 問題へのリンク 問題概要 長さ の文字列 が与えられる。次の 回のクエリに答えよ。 【クエリ】 整数 と文字 が与えられるので、 を に変更する。その後の文字列 の中に、"ABC" が何個含まれるかを答えよ。 制約 考えたこと…
二分探索:lower_bound
二分探索
数列
クエリ処理問題
NoviSteps4Q
鉄則本
鉄則本B問題
AtCoder
そのまま覚えたい典型問題
まずソートして考える
ソート
取得:個数
鉄則本★3
lower_bound() の練習!! 問題へのリンク 問題概要 長さ の配列 が与えられる。この配列に対して 回のクエリに答えよ。 【クエリ】 整数 が与えられるので、配列 の中に より小さい要素が何個あるかを求めよ。 制約 解法 github.com コード #include <bits/stdc++.h> using</bits/stdc++.h>…
NoviSteps2Q
AtCoder
鉄則本
鉄則本B問題
鉄則本★4
累積和
二次元累積和
【問題集】累積和
クエリ処理問題
二次元平面上のN点の問題
制約:数値が10^6以下
バケット
個数を0-1の総和として表現する
データ構造
取得:個数
二次元累積和の練習問題! 問題へのリンク 問題概要 二次元平面上に 個の点がある。 番目の点の座標は である。 「x 座標が 以上 以下で、y 座標が 以上 以下であるような点は何個あるか?」 というタイプの 回のクエリに答えよ。 制約 解法 x, y 座標の値が…
AtCoder
AtCoder300点
ABC-C
累積和
文字列
【問題集】累積和
バケット
クエリ処理問題
区間
データ構造テク:前処理
灰色diff
そのまま覚えたい易しい教育的典型問題
取得:区間
取得:個数
NoviSteps4Q
すごくよく似た過去問がある。これ → ABC 122 C - GeT AC 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。この文字列に対する次の 個のクエリに答えよ。 各クエリでは、文字列の区間 が与えられる。この区間を取り出した部分文字列に…