競技プログラミングにおけるWaveletMatrix問題まとめ

WaveletMatrix

• WaveletTreeというのもあるが、WMは完全上位互換らしいので、こっちを使えるようになろう
• （ウェーブレット行列は静的なものだが、動的にもできるし、永続化もできる）←どこを見て書いたんだろう
• 解説
• 実装例 antaさん Algoogleさん
• できること
  • quantile: 降順ソートしたときにk番目に大きい数を取ってくる
  • freqency: ある区間内にある範囲の数が何個あるか
  • 区間に含まれるk番目のvの位置も取れるらしい [beetさんの強ライブラリ](区間に含まれるvの数、区間に含まれるk番目のvの位置、区間内でk番目に大きい要素)
  • 重複要素を無視して、k番目に大きい数も取ってこれるテク

問題

静的ウェーブレット行列

• CodeChef Chef and Prime Queries 解説
• ECR22 Army Creation 解説
• SPOJ K-th Number
• yukicoder No.738 平らな農地
• yukicoder No.919 You Are A Project Manager 解説

以下、下書き同然

まだ解いてない問題

静的ウェーブレット行列

• CF381 Alyona and a Tree 解説
• HackerRank Coloring Tree
• CodeChef Yet Another SubSegment Sum Problem 解説
• CodeChef Easy Query 解説
• AOJ Hard Beans
• CF267 Alex and Complicated Task
• CodeChef Simple Queries
• CF433 Boredom 解説

以下平面上でのクエリ

• AOJ 宝探し
• CodeChef Triangular Queries 解説
• HackerRank Points and Fences 解説

動的ウェーブレット木

• http://d.hatena.ne.jp/hirokazu1020/20140801/1406924897

【発展的話題】 永続動的ウェーブレット行列

http://minpcontest.appspot.com/p/THEGTHNUMBER.html
http://minpcontest.appspot.com/e/THEGTHNUMBER.html
http://pekempey.hatenablog.com/entry/2016/05/16/235152

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2270
http://www.utpc.jp/2011/slides/l_th.pdf
http://d.hatena.ne.jp/anta1/20130202/1359761183