https://yukicoder.me/problems/no/542
続きを読む競技プログラミングにおけるセグメントツリー問題まとめ [セグメントツリー, BIT, 遅延評価セグメントツリー]
セグメントツリー
基礎問題
応用問題
遅延評価セグメントツリー([l,r)をvにする +α)
- yukicoder No. 318 学学学学学 (+総和)
- yukicoder No. 230 Splarraay スプラレェーイ (+総和)
- Codeforces Round #200 (Div. 1) D. Water Tree (+総和, HL分解と併用)
- HackerRank Bigger Arrays (+総積)
- Educatinonal Codeforces Round 6 E. New Year Tree (+総OR, EulerTourと併用)
- AOJ Dimension travel 解説
- AC Replace Digits
遅延評価セグメントツリー([l,r)にvを足す +α)
- JOI typhoon(+1要素get(ちなみに1要素getならBITでもできる))
- CODE FESTIVAL 2015 決勝 D. 足ゲームⅡ (+最大値)
- ARC 045 B. ドキドキデート大作戦高橋君 (+最小値)
- yukicoder No.631 Noelちゃんと電車旅行 解説(+最大値)
- 天下一プログラマーコンテスト 2016 予選B D. 天下一数列にクエリを投げます (+最小値, 考察が難しい)
- ARC 076 Exhausted? (+最大値, 考察が難しい)
- ABC 035 C. オセロ (+総和) 解説
- CSAcademy Constant Sum (+総和)
- yukicoder No. 399 動的な領主 (+総和, HL分解と併用)
- JOI かくれんぼ (Hide-and-seek) (+区間max with 最小添字)
遅延評価セグメントツリー(その他)
- NJPC2017 H. 白黒ツリー ([l,r)にxor1する + [l,r)の総和, HL分解も併用)
- square869120Contest #2 H. Counting 1's ([l,r)にxor1する + [l,r)の総和)
- RUPC2017 Day3 ブロッコリー?カリフラワー? (Broccoli or Cauliflower) 解説 ([l,r)にxor1する + [l,r)の総和)
- AOJ 2450. Do use segment tree HL分解も必要。人が解く問題じゃない。
- yukicoder No. 235 めぐるはめぐる(5) 係数がついている遅延セグメント木
- yukicoder No. 255 Splarrraaay スプラーレェーーイ 係数がついてて、区間が座圧されている遅延セグメント木
- CF442 Danil and a Part-time Job Euler Tour+遅延セグ木(バイナリでの区間xor,区間sum)
- HR Factorial Array 解説 (配列を乗せる+シフト+更新クエリ)
- CF538 Please, another Queries on Array? 解説 (区間積・区間総積、区間or・区間or)
- AC Deforestation 解説
- ABC128E Roadwork 解説
- HR Heavy Light 2 White Falcon 解説 (区間等差数列add, 区間sum)
- yukicoder No.1099 Range Square Sum (区間add、区間二乗和取得)
特殊なマージをするセグメント木
- CodeChef Chef and Subarray Queries 解説
- CF284 Traffic Jams in the Land 解説
- 半環問題
- CF179 Yaroslav and Points 解説
- CC Rotate Point
- yukicoder No.619 CardShuffle
- ECR35 Mass Change Queries
- yukicoder No.650 行列木クエリ 解説
- yukicoder No.776 A Simple RMQ Problem 解説
- HR Sweets Distribution(Hard)
- HR ビブンケイスウ 解説
動的構築セグメントツリー
シフトセグメントツリー
2Dセグメントツリー
3Dセグメントツリー
2DBIT
セグメントツリーにBITなどを載せるテク
- 手法解説の記事を書いた
- CF431 Goodbye Souvenir (BITを載せて矩形和を求める)
- ECR 33 Subtree Minimum Query (RMQを乗せて矩形minを求める)
- HR Mr. X and His Shots 解説
- yukicoder No.728 ギブ and テイク 解説
更新や取得を枝刈りしたり、更新回数が限られている関係で間に合う(奈良木?)
競技プログラミングにおける二分探索・三分探索問題まとめ [二分法]
~探索
- 二分探索は単調変化する関数に対して、YES/NOの境目を見つける探索 参考
- 三分探索は凸関数である関数に対して、最大値・最小値を見つける探索 参考1 参考2
- 二分探索・三分探索は気がつくまでが長い。単調性が無いかというのは常に考えておく
- 「最大値の最小化」
- リアクティブ問題と二分探索は相性がいい
- 二分探索+全探索の高速化の話 ここ ここも
- 【テク1】答えを二分探索で固定すると、x以上とx未満で0,1(または-1,1)になってうまく扱えるというテクがある(中央値と絡めてよく使う)
- 【テク2】「ある条件でソートしたときのK番目の数を求めよ」というのは、答えの数で二分探索するというものがある
- 【テク3】平均値っぽい分数最大化は二分探索
- 二分探索から単調性を引いたもの『二分法』
- 単調性がなくても、場合によっては境界を二分法で探すことができる
- 中央値の定理?
- 二分探索と区別するために便宜上二分法と言っているが、ほんとに言い方正しいか分かってない
問題
二分探索(実数)
- yukicoder No.67 よくある棒を切る問題 (1)
- JOI ski - スキー (Ski) 解説1 解説2
- CF532 NN and the Optical Illusion 解説
- 【テク3】ABC034D 食塩水
- 【テク3】AC おまかせ 解説
二分探索(整数)
- CSA55 Build the Fence 解説
- yukicoder No.168 ものさし
- yukicoder No.507 ゲーム大会(チーム決め)
- yukicoder No.648 お や す み 解説
- CF Too Easy Problems
- ECR27 Fire in the City
- 【テク2】ABC123 Cake 123 解説
- ECR32 K-Dominant Character
- ARC088 Christmas Tree 解説 (二分探索in二分探索)
- AC Maxmin Tour
- yukicoder No.702 中央値を求めよ LIMITED 解説
- 【テク1】ARC101 Median of Medians 解説
- 【テク1】【テク2】AOJ L番目のK番目の数 (LthKthNumber) 解説
- 【テク1】AGC006 Median Pyramid Hard
- HR Picu Bank
- AC Come Together 解説
- AC Snuke the Wizard 解説
- yukicoder No.814 ジジ抜き 解説
- 【テク2】yukicoder No.817 Coin donation 解説
三分探索
- yukicoder No.306 さいたま2008 (実数で最小値)
- yukicoder No.198 キャンディー・ボックス2 (整数で最小値)
- CodeChef Calculator (整数の最大値)
- HOJ Treasure Hunt(実数で最小値) 解説
- CF320 Weakness and Poorness (実数で最小値) 解説
- CSA73 Ricocheting Balls(整数で最小値)解説
- AOJ ヒバラ海に沈む遺跡 解説(実数で最大値)
二分法
【発展的話題】並列二分探索
- Parallel Binary Search 解説(英語)
- 複数の二分探索を1つに纏めるテクであるが、二分探索を纏めるというよりかは二分探索で同じような計算が沢山出てくるのでそれを1回に減らして二分探索していこうというモチベーション
- 永続化で対応できる場合もあるらしい
- 問題
- AGC002 Stamp Rally 解説1 解説2
- HR Selective Additions 解説
- AC Union Sets