drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AOJ HUPC データ構造 クエリ処理問題 平方分割 操作 単純化：操作の流れを単純化して考える ソート系データ構造 二分探索 二分探索:lower_bound データ構造テク：全体に反映させる値を別にもつ(遅延評価) 単純化：標準形を考える スタートを0としてよい 数列 平衡二分探索木 難しかったー！！平方分割かな...とまでは思ったので、もっと粘り強く考えられるようにならないと...！ 問題へのリンク 問題概要 長さ の数列 が与えられます。以下の 4 種類のクエリを 回処理してください。 クエリ 1: が与えられるので、 () を に更新する クエリ 2: が与えられるので、 () を に更新する クエリ 3: が与えられるので、 () を に更新する クエリ 4: が与えられるので、 かつ を満たす の個数を出力する 制約 考えたこと 平方分割系かなとは思った。でも、次のように考えてしまい、先に進めなかった。 各バケットごとにクエリ 1〜3 の操作列を保存しないといけな… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F09%2F14%2F192800" title="AOJ 3170 Freqs (HUPC 2020 day1-G) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2020-09-14 19:28:00 rich https://drken1215.hatenablog.com/entry/2020/09/14/192800 1.0 100%